Reconstructing phylogenies (evolutionary histories) of proteins from a set of observed sequences is an important statistical modelling task in molecular evolution. Maximum likelihood and Bayesian methods have been used for phylogenetic inference. We review Markov chain Monte Carlo schemes which have been developed, and discuss the application of these to HIV data. We consider the problem of analysing the results from one such sampler and describe in detail a method for determining a consensus labelled history. This is illustrated with an example of HIV protease.