High-quality Normalized Difference Vegetation Index (NDVI) time-series data are important for many regional and global ecological and environmental applications. Unfortunately, residual noise in current NDVI time-series products greatly hinders their further applications. Several noise-reduction methods have been proposed during the past two decades, but two important issues remain to be resolved. First, the methods usually perform poorly for cases of continuous missing data in the NDVI time series. Second, they generally assume negatively biased noise in the NDVI time series and thus erroneously raise some local low NDVI values in certain cases (e.g., the harvest period for multi-season crops).We therefore developed a new noise-reduction algorithm called the Spatial-Temporal Savitzky-Golay (STSG) method. The new method assumes discontinuous clouds in space and employs neighboring pixels to assist in the noise reduction of the target pixel in a particular year. The relationship between the NDVI of neighboring pixels and that of the target pixel was obtained from multi-year NDVI time series thanks to the accumulation of NDVI data over many years, which would have been impossible a decade ago. We tested STSG on 16-day composite MODIS NDVI time-series data from 2001 to 2016 in regions of mainland China and 11 phenology camera sites in North American. The results showed that STSG performed significantly better compared with four previous widely used methods (i.e., the Asymmetric Gaussian, Double Logistic, Fourier-based, and Savitzky-Golay filter methods). One obvious advantage was that STSG was able to address the problem of temporally continuous NDVI gaps. STSG effectively increased local low NDVI values and simultaneously avoided overcorrecting low NDVI values during the crop harvest period. In addition, implementing STSG required only raw MODIS NDVI time-series products without any additional burden of data requirements. All of these advantages make STSG a promising noise-reduction method for generating high quality NDVI time-series data.