The effect of potassium ferrate (PF) and straw fiber (SF) on the strength of cement-based solidified municipal sludge, including the influence of reducing the organic matter in the sludge on the efficiency of the hydration of the cement, was studied. Single-factor tests, orthogonal tests, and linear weighted optimization methods were used to obtain suitable ratios to meet practical requirements, and then SEM and XRD analyses were used to explore the solidification mechanism. The results showed that PF and SF had significant influence on the strength, with SF having the greatest influence and the strength increasing with the amount of both admixtures, and cement had no significant influence on the strength. After linear weighting optimization, the ideal dosage was found to be 20% cement, 20% PF, and 5% SF, which produced a solidified sludge that had an strength of 126.87 kPa, far higher than the 50 kPa required to qualify for disposal in landfills. Analysis of the mineral content and microstructure showed that PF and SF could promote cement hydration and produce more hydration products, and the density of the optimized sample was much higher than that of the raw sludge and a sludge sample mixed with 20% cement alone.