Water quality prediction plays an important role in the prevention and control of water pollution. In order to improve the accuracy of water quality prediction, a new prediction method based on the combination of random forest (RF) algorithm and long short-term memory (LSTM) neural network was proposed. Taking the water quality monitoring data of Taolinkou Reservoir as an example, the RF algorithm was used to screen out the key characteristics that affect the changes in the concentration of permanganate index (CODMn), ammonia nitrogen (NH3—N), total nitrogen (TN) and total phosphorus (TP). On this basis, a water quality prediction model based on RF-LSTM was constructed and the prediction results were then compared with those of sole LSTM, RF-BPNN, and RF-RNN model. The results show that the prediction performance of the RF-LSTM model is better than the other models with extremely high prediction accuracy and strong generalization ability, the coefficient of determination (R2) for predicting the concentration of CODMn, NH3—N, TN and TP in the next four hours are 0.986, 0.990, 0.989 and 0.988, respectively. The research results can provide a new approach for high-precision water quality prediction.