This study aims at the development of magnesium phosphate cement-based ultra-high performance concrete (MPC-UHPC). To this end, MPC paste phase was designed by using high magnesia-to-phosphate (M/P, 3.5) and low water-to-cement (W/C, 0.10–0.16) mass ratios, and certain amounts of ultra-fine fly ash (UFA, 5%–15%). Fresh and hardened properties, and microstructure of the developed MPC-UHPC were evaluated, and compared with those of conventional UHPC as well. Test results showed that lower W/C resulted in higher mechanical strengths and lower drying shrinkage, but the sharp decrease of workability and increase of autogenous shrinkage. At a constant W/C, the addition of UFA effectively improved fresh behaviors and decreased autogenous shrinkage without degrading late-age compressive strength. Due to a good plasticizing effect of UFA, the W/C could be reduced with increasing UFA content, leading in turn to continuous increase in autogenous shrinkage and strength. Compared to conventional UHPC, an optimal MPC-UHPC provided much lower shrinkage, higher early strength, and comparable 28-d strength above 120 MPa. Microstructural analyses revealed that a combination use of high M/P, low W/C and UFA as micro-filler can result in densely compacted microstructure, improved pore structure and enhanced matrix-aggregate interface, which is responsible for the superior mechanical performance of MPC-UHPC.