Summary: We study a new approach to image denoising based on complexity regularization. This technique presents a flexible alternative to the more conventional \(l^2\), \(l^1\), and Besov regularization methods. Different complexity measures are considered, in particular those induced by state-of-the-art image coders. We focus on a Gaussian denoising problem and derive a connection between complexity-regularized denoising and operational rate-distortion optimization. This connection suggests the use of efficient algorithms for computing complexity-regularized estimates. Bounds on denoising performance are derived in terms of an index of resolvability that characterizes the compressibility of the true image. Comparisons with state-of-the-art denoising algorithms are given.