In order to study the feasibility and sand substitution mechanism of cement mortar mixed with iron ore tailings (IOT), iron ore tailings cement mortars (referred to as IOTC) with IOT content of 0%, 25%, and 50% were made and tested. First, the basic properties of IOT used were measured to verify the theoretical feasibility. Second, the uniaxial compressive and tensile strengths, as well as the crack resistance performance of IOTC under different curing ages and different sand substitution rates were tested. Third, the techniques of inductively coupled plasma atomic emission spectrometry (ICP-OES), X-ray diffraction (XRD), nuclear magnetic resonance (NMR), scanning electron microscopy and energy-dispersive spectroscopy (SEM-EDS) were used to study the influence of curing age and different sand substitution rates on the chemical, mineralogical, and microstructural characteristics of IOTC. The sand substitution mechanism of IOT was then discussed. The research results proved the feasibility of using IOT to substitute standard sand in cement mortar. Within substitution rate of 0–50%, the mechanical properties increased with the increase of substitution rate. Though limited chemical effects were found by adding IOT, in comparison with standard sand mortar, more hydration products were found and the pore size distribution was changed for IOTC, which corresponds to its mechanical improvement.