Using evolutionary methodology for crystal structure prediction, we explore high-pressure phases of CaLi2, a compound made of two elements that show anomalies upon compression. In addition to the known low-pressure Laves phases, we find two novel structures with space groups C2/c and P2{1}/c, stable at pressure ranges of 35-54 GPa and 54-105 GPa, respectively. It is found that decomposition into pure elements is energetically favorable at pressures of 20-35 GPa and above 105 GPa. Such decomposition-recombination-decomposition oscillating behavior with pressure is predicted for the first time in a binary compound. The C2/c and P2{1}/c phases are predicted to be superconductors, and the calculated T{c} of approximately 15 K at 45 GPa is in good agreement with experiment.