Video background modeling is an important preprocessing step in many video analysis systems. Principal component pursuit (PCP), which is currently considered to be the state-of-the-art method for this problem, has a high computational cost, and processes a large number of video frames at a time, resulting in high memory usage and constraining the applicability of this method to streaming video. In this paper, we propose a novel fully incremental PCP algorithm for video background modeling. It processes one frame at a time, obtaining similar results to standard batch PCP algorithms, while being able to adapt to changes in the background. It has an extremely low memory footprint, and a computational complexity that allows real-time processing.