Phylogenetic analysis of mammalian species using mitochondrial protein genes has proved to be problematic in many previous studies. The high mutation rate of mitochondrial DNA and unusual base composition of several species has prompted us to conduct a detailed study of the composition of 69 mammalian mitochondrial genomes. Most major changes in base composition between lineages can be attributed to shifts between the proportions of C and T on the L-strand. These changes are significant at all codon positions and are shown to affect amino acid composition. Correlated changes in the base composition of the RNA loops and stems are also observed. Following up from previous studies, we investigate changes in the base composition of all 12 H-strand proteins and find that variability in proportions of C and T is correlated with location on the genome. Variation in base composition across genes and species is known to adversely affect the performance of phylogenetic inference methods. We have, therefore, developed a customized three-state general time-reversible DNA substitution model, implemented in the PHASE phylogenetic inference package, which lumps C and T into a composite pyrimidine state. We compare the phylogenetic tree obtained using the new three-state model with that obtained using a standard four-state model. Results using the three-state model are more congruent with recent studies using large sets of nuclear genes and help resolve some of the apparent conflicts between studies using nuclear and mitochondrial proteins.