To address the issues that environmental elements have a significant impact on total nitrogen (TN) in effluent throughout the wastewater treatment process, and existing analysis methods and instruments are difficult to measure in real-time, a soft sensor model based on the fractional-order difference algorithm (FDA) and the stochastic configuration network (SCN) is proposed for the soft measurement of effluent TN in wastewater treatment plants. First of all, the significance of the pertinent parameters impacting effluent TN is assessed by using the grey correlation analysis approach, and the predictors with high evaluation are screened out as input variables of the soft sensor model. Secondly, a method of data sampling based on FDA is employed to generate multiple training subsets to train each SCN sub-model in parallel, and fuse the output results of multiple sub-models according to combination rules as the output of the model. The proposed approach can increase the model’s generalizability and maintain data information while guaranteeing data stability. Finally, the soft sensor model is verified by the actual data of a wastewater treatment process and the data collected from the Ganges River, India. Compared with prediction models including SCN, ELM, FDA-ELM, CNN-LSTM, Elman, BP, LSTM, etc, the results indicate that after sampling the data by FDA, smaller model prediction errors and higher prediction accuracy can be obtained, which can achieve high accuracy prediction of effluent TN in wastewater treatment plants.