MrBayes is a popular software package for Bayesian phylogenetic inference, which uses an iterative approach to derive an evolutionary tree for a collection of species whose DNA sequences are known. Computationally, MrBayes is characterized by a large number of iterations, each composed of a set of tasks that isolated are not very time-consuming, but are globally computationally demanding. To accelerate the latest MrBayes 3.2, this paper presents MrBayes sMC³, which relies on the computational power of an heterogeneous CPU+GPU platform. For this, MrBayes sMC³ exploits both task and data-level parallelism while minimizing the overheads associated with kernel launches and CPU-GPU data transfers. Experimental results indicate that the proposed parallel approach, together with the proposed set of optimizations, allow for an application acceleration of up to 10x regarding the original MrBayes, and up to 3x regarding the Beagle Library. Furthermore, by analyzing the convergence rate of MrBayes sMC³ with that of the state-of-the-art approaches, a significant reduction in execution time is observed.