Ever since eukaryotes subsumed the bacterial ancestor of mitochondria, the nuclear and mitochondrial genomes have had to closely coordinate their activities, as each encode different subunits of the oxidative phosphorylation (OXPHOS) system. Mitochondrial dysfunction is a hallmark of aging, but its causes are debated. We show that, during aging, there is a specific loss of mitochondrial, but not nuclear, encoded OXPHOS subunits. We trace the cause to an alternate PGC-1α/β-independent pathway of nuclear-mitochondrial communication that is induced by a decline in nuclear NAD(+) and the accumulation of HIF-1α under normoxic conditions, with parallels to Warburg reprogramming. Deleting SIRT1 accelerates this process, whereas raising NAD(+) levels in old mice restores mitochondrial function to that of a young mouse in a SIRT1-dependent manner. Thus, a pseudohypoxic state that disrupts PGC-1α/β-independent nuclear-mitochondrial communication contributes to the decline in mitochondrial function with age, a process that is apparently reversible.