Fly ash is a waste produced during combustion of coal that is a significant fossil fuel source for electricity production. Main beneficial use of fly ash has been defined in cement and concrete industry. However, low-grade fly ashes (LGFA), due to their high carbon content and low glass content, can hardly be used in making cement or concrete. Magnesia-phosphate cement (MPC) is a promising but costly binder material for utilizations in repair works of degraded infrastructure and some functional applications. Low-grade fly ash is possible to be consumed in making LGFA-MPC binder, which will undoubtedly reduce the cost and bring additional environmental benefit. In this paper, an MPC paste with the magnesia-to-phosphate molar (M/P) ratio of 8 and a water-to-solid (W/S) ratio of 0.2 is selected as the reference, and a LGFA is used to replace 20%, 40% and 60% of the solid phase by volume, respectively, to examine this possibility. The compressive strengths of the four pastes are measured following the increasing ages, and the water resistance indices of them are also evaluated. The results show that the higher the fly ash replacement, the lower the compressive strength at all ages, but the better the long-term water-resistance. Based on a three-limit theory, the effect of fly ash replacement on compressive strength is explained, and it is proved that the fly ash is more than an inert filler. The influence of fly ash on water resistance is also explained through a microstructural analysis.