Across eukaryotic species, mild mitochondrial stress can have beneficial effects on the lifespan of organisms. Mitochondrial dysfunction activates an unfolded protein response (UPR^mt), a stress signaling mechanism designed to ensure mitochondrial homeostasis. Perturbation of mitochondria during larval development in C. elegans not only delays aging but also maintains UPR^mt signaling, suggesting an epigenetic mechanism that modulates both longevity and mitochondrial proteostasis throughout life. We identify the conserved histone lysine demethylases jmjd-1.2/PHF8 and jmjd-3.1/JMJD3 as positive regulators of lifespan in response to mitochondrial dysfunction across species. Reduction of function of the demethylases potently suppresses longevity and UPR^mt induction, while gain of function is sufficient to extend lifespan in a UPR^mt-dependent manner. A systems genetics approach in the BXD mouse reference population further indicates conserved roles of the mammalian orthologs in longevity and UPR^mt signaling. These findings illustrate an evolutionary conserved epigenetic mechanism that determines the rate of aging downstream of mitochondrial perturbations.