The paper presents a novel method for rapid quantification of uncertainty in history matching reservoir models using a two-stage Markov Chain Monte Carlo (MCMC) method. Our approach is based on a combination of fast linearized approximation to the dynamic data and the MCMC algorithm. In the first stage, we use streamline-derived sensitivities to obtain an analytical approximation in a small neighborhood of the previously computed dynamic data. The sensitivities can be conveniently obtained using either a finite-difference or streamline simulator. The approximation of the dynamic data is then used to modify the instrumental proposal distribution during MCMC. In the second stage, those proposals that pass the first stage are assessed by running full flow simulations to assure rigorousness in sampling. The uncertainty analysis is carried out by analyzing multiple models sampled from the posterior distribution in the Bayesian formulation for history matching. We demonstrate that the two-stage approach increases the acceptance rate, and significantly reduces the computational cost compared to conventional MCMC sampling without sacrificing accuracy. Finally, both 2D synthetic and 3D field examples demonstrate the power and utility of the two-stage MCMC method for history matching and uncertainty analysis.