CaFeO2, a material exhibiting an unprecedented layered structure containing 3d(6) iron in a high-spin distorted square-planar coordination, is reported. The new phase, obtained through a low-temperature reduction procedure using calcium hydride, has been characterized through powder neutron diffraction, synchrotron X-ray diffraction, Mossbauer spectroscopy, XAS experiments as well as first-principles DFT calculations. The XAS spectra near the Fe-K edge for the whole solid solution (Sr1-xCax)FeO2 supports that iron is in a square-planar coordination for 0 <= x <= 0.8 but clearly suggests a change of coordination for x = 1. The new structure contains infinite FeO2 layers in which the FeO4 units unprecedentedly distort from square-planar toward tetrahedra and rotate along the c-axis, in marked contrast to the well-studied and accepted concept that octahedral rotation in perovskite oxides occurs but the octahedral shape is kept almost regular. The new phase exhibits high-spin configuration and G-type antiferromagnetic ordering as in SrFeO2. However, the distortion of the FeO2 layers leads to only a slight decrease of the Neel temperature with respect to SrFeO2. First-principles DFT calculations provide a clear rationalization of the structural and physical observations for CaFeO2 and highlight how the nature of the cation influences the structural details of the AFeO(2) family of compounds (A = Ca, Sr, Ba). On the basis of these calculations the driving force for the distortion of the FeO2 layers in CaFeO2 is discussed.