Non-local mean (NLM) filtering proved to be an effective tool for noise reduction in natural and medical imaging. The technique relies on existing redundant information in the input image to discriminate the genuine signal from noise. However, due to the prohibitively long computation time, the search for finding similar information is confined by a predefined search window, which may hamper the performance of this filter. In this work, a spatially-guided non-local mean (SG-NLM) approach is proposed to overcome this issue. The proposed method was evaluated on whole-body PET images presenting with high noise levels, which adversely affect lesion detectability and quantitative accuracy.In the SG-NLM method, as opposed to the conventional NLM method, where a predefined search window is defined to confine exhaustive search for finding similar patterns, the information about similar patterns is extracted from the clustered version (created based on signal intensity levels) of the input image as well as information about prominent edges. The performance of the SG-NLM was evaluated against post-reconstruction NLM, Gaussian, bilateral and BayesShrink Wavelet denoising approaches. A digital phantom containing three small spheres mimicking lesions in the lung, experimental study using the Jaszczak phantom and whole-body PET/CT clinical studies were utilized to assess the performance of abovementioned denoising approaches.The SG-NLM method led to a signal-to-noise (SNR) increase from 21.3 (unfiltered PET image) to 30.1 in computer simulations of small lesions while the NLM mean filer resulted in an SNR of 29.4 (p<0.05). The experimental Jaszczak phantom study demonstrated that the contrast-to-noise ratio (CNR) increased from 11.3 when using the Gaussian filter to 18.6 and 19.5 when using NLM and SG-NLM filters (p<0.05), respectively. The superior performance of the SG-NLM approach was confirmed by the clinical studies where the bias in malignant lesions decreased to -2.3±1.1% compared to -11.7±2.4 and -2.9±1.1 achieved by the Gaussian and NLM methods (p<0.05), respectively.The proposed SG-NLM achieves promising compromise between noise reduction and signal preservation compared to the conventional NLM method. The superior performance of the SG-NLM method was accomplished without adding extra burden to the computational complexity of the conventional NLM filter, which makes it attractive for denoising PET images.