We address the prohibitively large cost of Markov chain Monte Carlo for uncertainty quantification in large-scale PDE applications with high dimensional parameter spaces. We propose a new multilevel Metropolis-Hastings algorithm, and give an abstract theorem on its cost. For a typical model problem in subsurface flow, we then provide a detailed analysis of the assumptions in the theorem and show gains of at least one order in the ϵϵ-cost over standard Metropolis-Hastings both theoretically and numerically. Note that in this talk we correct an error that we made in the preprint version of this paper and present a slightly modified algorithm to the one presented in earlier talks which eliminates the bias that the original algorithm introduced. This is joint work with A. Teckentrup (Warwick), C. Ketelsen (Boulder) and T. Dodwell (Bath).