The very high spectral resolution of Hyperspectral Images (HSIs) enables the identification of materials with subtle differences and the extraction subpixel information. However, the increasing of spectral resolution often implies an increasing in the noise linked with the image formation process. This degradation mechanism limits the quality of extracted information and its potential applications. This paper presents a new HSI denoising approach developed under the assumption that the clean HSI is low-rank and self-similar. Under these assumptions, the clean HSI admits extremely compact and sparse representations, which are exploited to derive a very fast and competitive denoising algorithm, named Fast Hyperspectral Denoising (FastHyDe), able to cope with Gaussian and Poissonian noise. In a series of experiments, the proposed approach competes with state-of-the-art methods, with much lower computational complexity.