Noise level estimation is crucial in many image processing applications such as blind image denoising. In this work, we propose a novel noise level estimation approach for natural images by jointly exploiting the piecewise stationarity and a regular property of the kurtosis in band-pass domains. We design a K-means based algorithm to adaptively partition an image into a series of non-overlapping regions, each of whose clean versions is assumed to be associated with a constant kurtosis throughout scales. The noise level estimation is then formulated as a problem to optimally fit this new kurtosis model. Experimental results show that our method can reliably estimate the noise level for a variety of noise types, and outperforms some state-of-the-art techniques, especially for non-Gaussian noises.