Monitoring the water contaminants is of utmost importance in water resource management. Prediction of the total dissolved solid (TDS) is particularly essential for water quality management and planning in the areas exposed to a mixture of pollutants. TDS primarily includes inorganic minerals and organic matters, and various salts and increasing the concentration of TDS causes the esthetic problems. The reflection of the pollutant burden of the aquatic system can remarkably determined by TDS magnitudes. This study focuses on the prediction of TDS and several biochemical parameters such as Na, Ca, HCO3, and Mg in a river system. To overcome nonstationarity, randomness, and nonlinearity of the TDS data, a multi-step supervised machine learning evolutionary algorithm (MSMLEA) is proposed to improve the model's performance at two gaging stations, namely Rig-Cheshmeh and Soleyman-Tangeh, in the Tajan River, Iran. In addition, a hybrid model that recruits intrinsic time-scale decomposition (ITD) for frequency resolution of the input data as well as a multivariate adaptive regression spline (MARS) were adopted. A novel metaheuristic optimization algorithm, crow search algorithm (CSA), was also implemented to compute the optimal parameter values for the MARS model. To validate the proposed hybrid model, standalone MARS, empirical mode decomposition (EMD)-based models, and hybrid ITD-MARS as well as a MARS-CSA were considered as the benchmark models. Results suggest the ITD-MARS-CSA outperforms other models.