This paper proposes online-learning complex-valued neural networks (CVNNs) to predict future channel states in fast-fading multipath mobile communications. CVNN is suitable for dealing with a fading communication channel as a single complex-valued entity. This framework makes it possible to realize accurate channel prediction by utilizing its high generalization ability in the complex domain. However, actual communication environments are marked by rapid and irregular changes, thus causing fluctuation of communication channel states. Hence, an empirically selected stationary network gives only limited prediction accuracy. In this paper, we introduce regularization in the update of the CVNN weights to develop online dynamics that can self-optimize its effective network size by responding to such channel-state changes. It realizes online adaptive, highly accurate and robust channel prediction with dynamical adjustment of the network size. We demonstrate its online adaptability in simulations and real wireless-propagation experiments.