Estimating the number of vehicles present in traffic video sequences is a common task in applications such as active traffic management and automated route planning. There exist several vehicle counting methods such as Particle Filtering or Headlight Detection, among others. Although Principal Component Pursuit (PCP) is considered to be the state-of-the-art for video background modeling, it has not been previously exploited for this task. This is mainly because most of the existing PCP algorithms are batch methods and have a high computational cost that makes them unsuitable for real-time vehicle counting. In this paper, we propose to use a novel incremental PCP-based algorithm to estimate the number of vehicles present in top-view traffic video sequences in real-time. We test our method against several challenging datasets, achieving results that compare favorably with state-of-the-art methods in performance and speed: an average accuracy of 98% when counting vehicles passing through a virtual door, 91% when estimating the total number of vehicles present in the scene, and up to 26 fps in processing time.