Images of outdoor scenes captured in bad weathers are often plagued by the limited visibility and poor contrast, and such degradations are spatially-varying. Differing from most previous dehazing approaches that remove the haze effect in spatial domain and often suffer from the noise problem, this paper presents an efficient multi-scale correlated wavelet approach to solve the image dehazing and denoising problem in the frequency domain. To this end, we have heuristically found a generic regularity in nature images that the haze is typically distributed in the low frequency spectrum of its multi-scale wavelet decomposition. Benefited from this separation, we first propose an open dark channel model (ODCM) to remove the haze effect in the low frequency part. Then, by considering the coefficient relationships between the low frequency and high frequency parts, we employ the soft-thresholding operation to reduce the noise and synchronously utilize the estimated transmission in ODCM to further enhance the texture details in the high frequency parts adaptively. Finally, the haze-free image can be well restored via the wavelet reconstruction of the recovered low frequency part and enhanced high frequency parts correlatively. The proposed approach aims not only to significantly increase the perceptual visibility, but also to preserve more texture details and reduce the noise effect as well. The extensive experiments have shown that the proposed approach yields comparative and even better performance in comparison with the state-of-the-art competing techniques.