Developing green mining technology for medium-to low-grade mines requires achieving minimal or no damage to the mining area’s ecological environment. A medium-to low-grade phosphate mine in Hubei Province was taken as the research object in this study. The tailings were selected as the main filling aggregate. Indoor tests and theoretical analysis were conducted to analyze the influence of curing age, the water–cement ratio, the cement–sand ratio, and slurry concentration on the strength of the cemented backfill. Furthermore, a multi-factor non-linear mathematical model of the strength of the cementitious filler was established. The study results indicated that the strength of backfill increased linearly with the increase in the curing age, decreased negatively with the increase in the water–cement ratio, and increased exponentially with the increase in the cement–sand ratio and the slurry concentration. The multivariate non-linear prediction model of the strength of the filling body at different ages was also established based on the test results. This predictive model could effectively predict the strength of the cemented backfill, and the error value was not larger than 4%. Our research results can lay a theoretical foundation for developing medium-to low-grade phosphate mine filling with tailings as the main filling aggregate.