We present two new models of protein sequence evolution based on structural properties of mitochondrial proteins. We compare these models with others currently used in phylogenetic analyses, investigating their performance over both short and long evolutionary distances. We find that our models that incorporate secondary structure information from mitochondrial proteins are statistically comparable with existing models when studying 13 mitochondrial protein data sets from eutherian mammals. However, our models give a significantly improved description of the evolutionary process when used with 12 mitochondrial proteins from a broader range of organisms including fungi, plants, protists, and bacteria. Our models may thus be of use in estimating mitochondrial protein phylogenies and for the study of processes of mitochondrial protein evolution, in particular for distantly related organisms.