We present a general-purpose variational method for online state estimation and parameter learning in state-space models (SSMs), a ubiquitous class of dynamic latent variable models for sequential data. As per standard batch variational techniques, we use stochastic gradients to simultaneously optimize a lower bound on the log evidence with respect to both model parameters and a variational approximation. However, unlike existing approaches, our method is able to operate in an entirely online manner, such that historic observations do not require revisitation after being incorporated and the cost of updates at each time step remains constant, despite the growing dimensionality of the posterior. This is achieved by utilizing a non-standard decomposition of this posterior distribution, and corresponding non-standard factorization of our variational approximation, followed by a novel adaptation of recursive value functions from the reinforcement learning literature. We demonstrate the performance of this methodology across several examples, including high-dimensional SSMs and sequential variational auto-encoders.