In this talk I will address the prohibitively large cost of Markov chain Monte Carlo methods for uncertainty quantification in large-scale PDE applications with high (or infinite) dimensional parameter spaces. We propose a new multilevel Metropolis-Hastings algorithm, and give an abstract theorem on its cost. We then provide a detailed analysis of the assumptions in the theorem for a typical model problem in subsurface flow, and show gains of at least one order in the ε-cost over standard Metropolis-Hastings both theoretically and numerically. This is joint work with T. Dodwell (Exeter), C. Ketelsen (Boulder) and A. Teckentrup (Warwick).