We derive a Markov chain to sample from the posterior distribution for a phylogenetic tree given sequence information from the corresponding set of organisms, a stochastic model for these data, and a prior distribution on the space of trees. A transformation of the tree into a canonical cophenetic matrix form suggests a simple and effective proposal distribution for selecting candidate trees close to the current tree in the chain. We illustrate the algorithm with restriction site data on nine plant species, then extend to DNA sequences from thirty-two species of fish. the algorithm mixes well in both examples from random starting trees, generating reproducible estimates and credible sets for the path of evolution.