Online Robust Matrix Factorization (ORMF) algorithms seek to learn a reduced number of latent features as well as outliers from streaming data sets. It is important to understand stability of online algorithms for dependent data streams since these are often generated by Markov chain Monte Carlo (MCMC) algorithms, but rigorous convergence analysis of most online algorithms were limited to independently obtained data samples. In this talk, we propose an algorithm for ORMF and prove its almost sure convergence to the set of critical points of the expected loss function, even when the data matrices are functions of some underlying Markov chain satisfying a mild mixing condition. We illustrate our results through dictionary learning and outlier detection problem for images and networks.