Considering the problem that structure information can be easily lost when the edge and texture regions of image are denoised by the Non-Local Means (NL-Means) denoising algorithm, and a NL-Means image denoising algorithm based on edge detection is proposed in this paper. Firstly the edge detection in the noise image is got by using the improved Sobel operator, and then the detecting result is used to improve the weight function of NL-Means algorithm. To make the neighborhoods with similar structure obtain more weight, not only the weighted Euclidean distance but also the edge structure are considered when the similarity of neighborhoods is measured. Experimental results demonstrate that our algorithms performance is superior to the NL-Means algorithm.