Bayesian methods can quantify the model uncertainty that is inherent in inversion of highly nonlinear geophysical problems. In this approach, a model likelihood function based on knowledge of the data noise statistics is used to sample the posterior model distribution, which conveys information on the resolvability of the model parameters. Because these distributions are multidimensional and nonlinear, we used Markov chain Monte Carlo methods for highly efficient sampling. Because a single Markov chain can become stuck in a local probability mode, we run various randomized Markov chains independently. To some extent, this problem can be mitigated by running independent Markov chains, but unless a very large number of chains are run, biased results may be obtained. We got around these limitations by running parallel, interacting Markov chains with “annealed” or “tempered” likelihoods, which enable the whole system of chains to effectively escape local probability maxima. We tested this approach using a transdimensional algorithm, where the number of model parameters as well as the parameters themselves were treated as unknowns during the inversion. This gave us a measure of uncertainty that was independent of any particular parameterization. We then subset the ensemble of inversion models to either reduce uncertainty based on a priori constraints or to examine the probability of various geologic scenarios. We demonstrated our algorithms’ fast convergence to the posterior model distribution with a synthetic 1D marine controlled-source electromagnetic data example. The speed up gained from this new approach will facilitate the practical implementation of future 2D and 3D Bayesian inversions, where the cost of each forward evaluation is significantly more expensive than for the 1D case.