The ratio between fly ash (FA) and magnesia is an important factor for the optimum design of FA blended magnesium potassium phosphate cements (MKPCs). In this study, a high CaO content FA (CaO = 12.5 wt%) was used to partially replace magnesia at 0 wt%, 30 wt%, 50 wt%, 70 wt%, and 90 wt%, respectively. The experimental results showed that a FA replacement of 50 wt% led to the highest compressive strengths. A FA replacement of 70 wt% is considered as upper limit, as the presence of more FA caused significantly lower strength. In the plain and the FA blended MKPCs, K-struvite (MgKPO4∙6H2O) was the main hydrate. At very high FA contents, additional calcium potassium hydrogen phosphate (CaK3H(PO4)2) was observed as well as the destabilization of K-struvite to cattiite (Mg3(PO4)2∙22H2O), which could be one of the main factors responsible for the lower strength of high FA blended MKPC mortars stored under water.