We present a novel, probabilistic algorithm for image noise removal. We show that suitably constrained random walks over small image neighborhoods provide a good estimate of the appearance of a pixel, and that a stable estimate can be obtained with a small number of samples. We provide a through evaluation and comparison of the proposed algorithm over a large standardized data set. Results show that our method consistently outperforms competing approaches for image denoising. http://www.cs.utoronto.ca/~strider/Denoise/BMVC_denoise.pdf