Experimental studies established that calcium undergoes several counterintuitive transitions under pressure: fcc rightarrow bcc rightarrow simple cubic rightarrow Ca-IV rightarrow Ca-V, and becomes a good superconductor in the simple cubic and higher-pressure phases. Here, using ab initio evolutionary simulations, we explore the behavior of Ca under pressure and find a number of new phases. Our structural sequence differs from the traditional picture for Ca, but is similar to that for Sr. The {beta}-tin (I41/amd) structure, rather than simple cubic, is predicted to be the theoretical ground state at 0 K and 33-71 GPa. This structure can be represented as a large distortion of the simple cubic structure, just as the higher-pressure phases stable between 71 and 134 GPa. The structure of Ca-V, stable above 134 GPa, is a complex host-guest structure. According to our calculations, the predicted phases are superconductors with Tc increasing under pressure and reaching ~20 K at 120 GPa, in good agreement with experiment.