Variation in rates of molecular evolution now appears to be widespread. The demonstration that body size is correlated with rates of molecular evolution suggests that physiological and ecological factors may be involved in molecular rate variation, but large-scale comparative studies are still lacking. Here, we use complete cytochrome b sequences from 85 species of tube-nosed seabirds (order Procellariiformes) and 5 outgroup species of penguins (order Sphenisciformes) to test for an association between body mass and rates of molecular evolution within the former avian order. Cladistic analysis of the 90 sequences estimates a phylogeny largely consistent with the traditional taxonomy of the Procellariiformes. The Diomedeidae, Procellariidae, and Pelecanoididae are monophyletic, while the Hydrobatidae are basal and paraphyletic. However, the two subfamilies within the Hydrobatidae (Hydrobatinae and Oceanitinae) are monophyletic. A likelihood ratio test detects significant deviation from clocklike evolution in our data. Using a sign test for an association between body mass and branch length in the seabird phylogeny, we find that larger taxa tend to have shorter terminal branch lengths than smaller taxa. This observation suggests that rates of mitochondrial DNA evolution are slower for larger taxa. Rate calibrations based on the fossil record reveal concordant body size effects. We interpret these results as evidence for a metabolic rate effect, as the species in this order exhibit large differences in metabolic rates, which are known to be highly correlated with body mass in this group. Our results support previous findings of body size effects and show that this effect can be significant even within a single avian order. This suggests that even lineage-specific molecular clocks may not be tenable if calibrations involve taxa with different metabolic rates.