Changes in histone modifications are an attractive model through which environmental signals, such as diet, could be integrated in the cell for regulating its lifespan. However, evidence linking dietary interventions with specific alterations in histone modifications that subsequently affect lifespan remains elusive. We show here that deletion of histone N-alpha-terminal acetyltransferase Nat4 and loss of its associated H4 N-terminal acetylation (N-acH4) extend yeast replicative lifespan. Notably, nat4Δ-induced longevity is epistatic to the effects of calorie restriction (CR). Consistent with this, (i) Nat4 expression is downregulated and the levels of N-acH4 within chromatin are reduced upon CR, (ii) constitutive expression of Nat4 and maintenance of N-acH4 levels reduces the extension of lifespan mediated by CR, and (iii) transcriptome analysis indicates that nat4Δ largely mimics the effects of CR, especially in the induction of stress-response genes. We further show that nicotinamidase Pnc1, which is typically upregulated under CR, is required for nat4Δ-mediated longevity. Collectively, these findings establish histone N-acH4 as a regulator of cellular lifespan that links CR to increased stress resistance and longevity.