Recently, an unexpected, positive correlation between the rate of evolution of mitochondrial proteins and longevity was reported. Here we re-analyze this relationship in various mammalian lineages using a bayesian phylogenetic analysis of amino-acid sequences, allowing for variable evolutionary rates across sites and species. A negative relationship between protein evolutionary rate and species longevity is reported for all oxidative phosphorylation complexes. A detailed analysis of the cytochrome b in 528 mammals reinforced this result, which contradicts previous publications. Reconducting the analysis in birds yielded similar results. We explain the discrepancy between this and previous reports by our improved taxon sampling and more appropriate methodology: unlike distance-based methods, the tree-based bayesian approach can take into account the high variation of substitution rate across amino-acid sites, and the resulting multiple substitution events. We discuss how our analysis contradicts Rottenberg's rationale, but does not dismiss his proposal of a longevity-dependent selective pressure on mitochondrial mutation rate in mammals and birds. This is because his interpretation invokes adaptation as the single evolutionary force at work, disregarding the effects of mutation, genetic drift, and purifying selection.