The role of genetic factors in the determination of lifespan is undisputed. However, numerous successful efforts to identify individual genetic modulators of longevity have not yielded yet a quantitative measure to estimate the lifespan of a species from scratch, merely based on its genomic constitution. Here, we report on a meta-examination of genome sequences from 248 animal species with known maximum lifespan, including mammals, birds, fish, insects, and helminths. Our analysis reveals that the frequency with which cysteine is encoded by mitochondrial DNA is a specific and phylogenetically ubiquitous molecular indicator of aerobic longevity: long-lived species synthesize respiratory chain complexes which are depleted of cysteine. Cysteine depletion was also found on a proteome-wide scale in aerobic versus anaerobic bacteria, archaea, and unicellular eukaryotes; in mitochondrial versus hydrogenosomal sequences; and in the mitochondria of free-living, aerobic versus anaerobic-parasitic worms. The association of longevity with mitochondrial cysteine depletion persisted after correction for body mass and phylogenetic interdependence, but it was uncoupled in helminthic species with predominantly anaerobic lifestyle. We conclude that protein-coding genes on mitochondrial DNA constitute a quantitative trait locus for aerobic longevity, wherein the oxidation of mitochondrially translated cysteine mediates the coupling of trait and locus. These results provide distinct support for the free radical theory of aging.