Phylogibbs is an algorithm for discovering regulatory sites in a collection of DNA sequences, including multiple alignments of orthologous sequences from related organisms.The algorithm uses a Gibbs sampling strategy, takes the phylogenetic relationships of the input sequences rigorously into account, and assigns realistic posterior probabilities to reported sites using a novel annealing+tracking strategy.