This work studies the recursive robust principal components analysis (PCA) problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, $S_t$, in the presence of large but structured (dense and low-dimensional) noise, $L_t$. We introduce a novel solution approach called ReProCS. Under mild assumptions and a denseness assumption on the unestimated subspace at various times, we show that, with high probability (w.h.p.), ReProCS can exactly recover the support set of $S_t$ at all times; and the reconstruction errors of both $S_t$ and $L_t$ are upper bounded by a time-invariant and small value.