Lead (Pb) and arsenic (As) contaminated soil poses severe threats to human health. This study proposes a novel approach for synchronous stabilisation/solidification (S/S) of Pb and As contaminated soil and explains the immobilisation mechanisms in red mud-modified magnesium phosphate cement (MPC). Experimental results show that incorporation of red mud in MPC binder retarded over-rapid reaction and enhanced compressive strength via the formation of (Al,Fe,K)PO₄·nH₂O compounds as indicated by X-ray diffractometer (XRD) and elemental mapping. The presence of Pb had a marginal effect on the MPC reaction; however, the presence of As suppressed the generation of MgKPO₄·6H₂O, leading to a significant delay of setting time and a reduction of compressive strength. Extended X-ray absorption fine structure (EXAFS) analysis proved that Pb²⁺ strongly coordinated with the PO₄^3–, whereas AsO₂– gently coordinated with K⁺. The MPC binder displayed an excellent immobilisation efficiency for Pb (99.9%), but was less effective for As. The use of red mud enhanced the As immobilisation efficacy to 80.5% due to strong complexation between AsO₂– and Fe³⁺. The treated soils fulfilled requirements of metal(loid) leachability and mechanical strength for on-site reuse. Therefore, red mud-modified MPC can be an effective binder for sustainable remediation of Pb and As contaminated soil.