This paper presents a flexible structure Radial Basis Function (RBF) neural network (FS-RBFNN) and its application to water quality prediction. The FS-RBFNN can vary its structure dynamically in order to maintain the prediction accuracy. The hidden neurons in the RBF neural network can be added or removed online based on the neuron activity and mutual information (MI), to achieve the appropriate network complexity and maintain overall computational efficiency. The convergence of the algorithm is analyzed in both the dynamic process phase and the phase following the modification of the structure. The proposed FS-RBFNN has been tested and compared to other algorithms by applying it to the problem of identifying a nonlinear dynamic system. Experimental results show that the FS-RBFNN can be used to design an RBF structure which has fewer hidden neurons; the training time is also much faster. The algorithm is applied for predicting water quality in the wastewater treatment process. The results demonstrate its effectiveness.