Recently, more and more traditional services are being migrated into a cloud computing environment that makes the quality of service (QoS) becomes an important factor for service selection and optimal service composition while forming cross-cloud service applications. Considering the nonlinear and dynamic property of QoS data, it is so difficult to achieve dynamic prediction while designing a QoS prediction method with unsatisfactory prediction accuracy. It is thus desirable to explore how to design an effective approach by incorporating some intelligent techniques into the QoS prediction method to improve prediction performance. In this paper, motivated by the adaptive critic design and Q-learning technique, we propose a novel QoS prediction approach to serve this purpose through the combination of fuzzy neural networks and adaptive dynamic programming (ADP), i.e., an online learning scheme. This approach extracts fuzzy rules from QoS data and employs the ADP method to parameter learning of the fuzzy rules. Moreover, we provide a convergence boundedness result for our proposed approach to guarantee the stability. Experimental results on a large-scale QoS service data set verify the prediction accuracy of our proposed approach.