The problem of uncertainty quantification for inverse problems presents many interesting challenges for the computational scientist. In this chapter, we present an efficient Markov Chain Monte Carlo (MCMC) sampling scheme for use on large-scale inverse problems with Poisson-distributed data. The MCMC method utilizes a “randomize-then-optimize” approach, which yields a sample of the unknown image with each application of the optimizer, and conjugate samples of the regularization parameter. The output from the MCMC method is then used to obtain an estimate of the unknown image via the sample mean, a measure of image uncertainty via the sample variance, as well as a sample density and credibility interval for the regularization parameter. The method is tested on examples from inverse problems: one- and two-dimensional image deblurring and positron emission tomography. In all cases, the method works well, is efficient for high-dimensional problems, and yields estimates and uncertainty measurements of both the unknown image and regularization parameter.