Sodium iron phospho-olivine, NaFePO4, is a promising cathode material for Na-ion batteries. However, Na-ion extraction and intercalation induce a large discontinuous volume change (>10 vol %), which leads to large transformation strains and may hamper the rate capability as well as the cyclic stability of NaFePO4. In the Li-ion counterpart LiFePO4, the size of the discontinuous volume change can be effectively reduced by substitution of Mn onto the Fe sites in the phospho-olivine structure, i.e., LiMnyFe1-yPO4 solid solution. In this paper, we investigate the battery performance and phase evolution during Na-ion storage in a series of MnyFe1-yPO4 (y = 0.0, 0.1, 0.2, 0.4, 0.6, and 0.8) cathode materials. Substitution of 10-20% of the Fe by Mn enhances the capacity by >15%. Using operando powder X-ray diffraction, we discover that the charge-discharge transformation strains are significantly reduced by stabilization of a NazMnyFe1-yPO4 solid solution over a wide Na compositional range. This effect even leads to a complete continuous solid solution transformation covering the entire charge process, which shows that the effect of Mn substitution is a highly effective route for reducing intercalation strains even during intercalation of the relatively large Na-ion.