Using a variable-composition ab initio evolutionary algorithm implemented in the USPEX code, we have performed a systematic search for stable compounds in the Ca-Bi system at different pressures. In addition to the well-known tI12-Ca2Bi and oS12-CaBi2, a few more structures were found by our calculations, among which phase transitions were also predicted in Ca2Bi (tI12 → oI12 → hP6), Ca3Bi2 (hP5 → mC20 → aP5) and CaBi (tI2 → tI8), as well as a new phase (Ca3Bi) with a cF4 structure. All the newly predicted structures can be both dynamically and thermodynamically stable with increasing pressure. The superconductive properties of cF4-CaBi3, tI2-CaBi and cF4-Ca3Bi were studied and the superconducting critical temperature Tc can be as high as 5.16, 2.27 and 5.25 K, respectively. Different superconductivity behaviors with pressure increasing have been observed by further investigations.