Dietary restriction (DR) increases lifespan and attenuates age-related phenotypes in many organisms; however, the effect of DR on longevity of individuals in genetically heterogeneous populations is not well characterized. Here, we describe a large-scale effort to define molecular mechanisms that underlie genotype-specific responses to DR. The effect of DR on lifespan was determined for 166 single gene deletion strains in Saccharomyces cerevisiae. Resulting changes in mean lifespan ranged from a reduction of 79% to an increase of 103%. Vacuolar pH homeostasis, superoxide dismutase activity, and mitochondrial proteostasis were found to be strong determinants of the response to DR. Proteomic analysis of cells deficient in prohibitins revealed induction of a mitochondrial unfolded protein response (mtUPR), which has not previously been described in yeast. Mitochondrial proteotoxic stress in prohibitin mutants was suppressed by DR via reduced cytoplasmic mRNA translation. A similar relationship between prohibitins, the mtUPR, and longevity was also observed in Caenorhabditis elegans. These observations define conserved molecular processes that underlie genotype-dependent effects of DR that may be important modulators of DR in higher organisms.