Stabilization and solidification of the waste phosphate sludge (WPS) using Portland cement (PC) and fly ash (FA) were studied in the present work. The WPS content in the cement mortars varied from 5% to 15%. Setting times were measured, and unconfined compressive strengths (UCS) were determined for the mortars cured in water for 3, 7, 28, 56, and 90 days. Zinc and nickel leaching of the solidified products were measured according to the Toxicity Characteristic Leaching Procedure. Setting times were extended as the WPS content in the paste samples increased. The UCS values of the mortar containing 5% WPS solidified by using 95% PC were similar to the reference sample. Use of 10% FA as cement substitute increased the UCS values by 10% at the end of curing period of 56 days. The WPS contained initially 130.2 mg L−1 of zinc and 22.7 mg L−1 of nickel. The zinc and nickel leached from the 5% WPS solidified by using 95% PC were measured as 3.8 mg L−1 and 0.4 mg L−1, respectively. These metal concentrations were below the limits given by the U.S. Environmental Protection Agency for landfilling the solidified wastes.