Many image-denoising approaches seek to remove either additive white Gaussian noise (AWGN) or impulse noise (IN), because both types are easier to process when considered separately. However, images can be corrupted by a mixture of AWGN and IN during image acquisition and transmission. The major difficulty of mixed noise removal arises through the complex distribution of noise, which cannot be fitted by a simple parametric model. In this paper, a new nonlocal means based framework (NMF) is proposed. A median-type filter is used to detect the locations of outlier pixels; these pixels are then replaced by their nonlocal means, which makes the mixed noise distribution approximately Gaussian. To prove the effectiveness of our NMF, a low rank approximation combined with NMF (LRNM) model is presented for mixed noise removal. In the LRNM, we group similar nonlocal patches in a matrix and apply a low rank approximation to reconstruct the clean image. Gradient regularization is added to better preserve the image texture details. A convolutional neural network (CNN) combined with the NMF (NMF-CNN) is also presented, to prove the generality of the NMF. Experimental results show that LRNM and NMF-CNN achieve a strong mixed noise removal performance and also produce visually pleasing denoising results.