We describe a Bayesian approach to infer phylogeny and ancestral genome arrangements on the basis of genome arrangement data using a model in which gene inversion is the sole mechanism of change. A Bayesian approach provides a means to quantify the uncertainty in the phylogeny and in the ancestral genome arrangements. We describe a method of sampling phylogenies from the posterior distribution via Markov chain Monte Carlo (MCMC) that is computationally feasible for large data sets. We compare and contrast this MCMC approach with methods which reconstruct maximum parsimony phylogenies from genome arrangement data and demonstrate several advantages of a Bayesian approach to this problem. Furthermore, we have found that our sampler has discovered many genome rearrangement scenarios that require fewer gene inversions on a Campanulaceae cpDNA data set than other published reconstructions which were thought to be most parsimonious.