Host–pathogen conflicts leave genetic signatures in genes that are critical for host defense functions. Using these “molecular scars” as a guide to discover gene functions, we discovered a vertebrate-specific MItochondrial STress Response (MISTR) circuit. MISTR proteins are associated with electron transport chain (ETC) factors and activated by stress signals such as interferon gamma (IFNγ) and hypoxia. Upon stress, ultraconserved microRNAs (miRNAs) down-regulate MISTR1(NDUFA4) followed by replacement with paralogs MItochondrial STress Response AntiViral (MISTRAV) and/or MItochondrial STress Response Hypoxia (MISTRH). While cells lacking MISTR1(NDUFA4) are more sensitive to chemical and viral apoptotic triggers, cells lacking MISTRAV or expressing the squirrelpox virus-encoded vMISTRAV exhibit resistance to the same insults. Rapid evolution signatures across primate genomes for MISTR1(NDUFA4) and MISTRAV indicate recent and ongoing conflicts with pathogens. MISTR homologs are also found in plants, yeasts, a fish virus, and an algal virus indicating ancient origins and suggesting diverse means of altering mitochondrial function under stress. The discovery of MISTR circuitry highlights the use of evolution-guided studies to reveal fundamental biological processes.