Abstract Motivation: Bayesian phylogenetic inference can be used to propose a ‘tree of life’ for a collection of species whose DNA sequences are known. While there are many packages available that implement Bayesian phylogenetic inference, such as the popular MrBayes, running these programs poses significant computational challenges. Parallelized versions of the Metropolis coupled Markov chain Monte Carlo (MC3) algorithm in MrBayes have been presented that can run on various platforms, such as a graphics processing unit (GPU). The GPU has been used as a cost-effective means for computational research in many fields. However, until now, some limitations have prevented the GPU from being used to run MrBayes MC3 effectively. Results: We give an appraisal of the possibility of realistically implementing MrBayes MC3 in parallel on an ordinary four-core desktop computer with a GPU. An earlier proposed algorithm for running MrBayes MC3 in parallel on a GPU has some significant drawbacks (e.g. too much CPU–GPU communication) which we resolve. We implement these improvements on the NVIDIA GeForce GTX 480 as most other GPUs are unsuitable for running MrBayes MC3 due to a range of reasons, such as having insufficient support for double precision floating-point arithmetic. Experiments indicate that run-time can be decreased by a factor of up to 5.4 by adding a single GPU (versus state-of-the-art multicore parallel algorithms). We can also achieve a speedup (versus serial MrBayes MC3) of more than 40 on a sufficiently large dataset using two GPUs. Availability: GPU MrBayes (i.e. the proposed implementation of MrBayes MC3 for the GPU) is available from http://mrbayes-gpu.sourceforge.net/. Contact: liuxg74@yahoo.com.cn Supplementary information: Supplementary data are avaliable at Bioinformatics online.