In order to eliminate the cloud and mist from remote sensing images captured by cameras, a new non-local means algorithm is proposed to process the cloud and mist noise in remote sensing images. Based on the gradient feature under the shadow of cloud and mist in the remote sensing images, it is found that the intensity of the image declines obviously while the gradient only has a little change,therefore, the gradient information can be coupled into the weight computation. Then, the redundant information in image sequences is used to compute the new weights and the new weights are used to restore the image sequences. Two remote sensing image sequences are taken by UltraCamD in Xinjiang and Shanxi in China, and results show that the quality of restored image is improved significantly by this algorithm. Compared with the original images,the PSNR by proposed method has improved by more than 9 dB. Experiments show that the proposed algorithm can effectively restore remote sensing images without the motion estimation for the cloud and camera as well as the noise model.