The Holocene thermal maximum, a period of global warmth evident in early to mid-Holocene proxy reconstructions, is controversial. Most model simulations of the Holocene have not reproduced this warming, leading to a disagreement known as the Holocene Temperature Conundrum. Pollen records document the expansion of vegetation in the early and mid-Holocene African Sahara and Northern Hemisphere mid- and high latitudes, which has been overlooked in previous modeling studies. Here, we use time slice simulations of the Community Earth System Model to assess the impact of Northern Hemisphere vegetation change on Holocene annual mean temperatures. Our simulations indicate that expansion of Northern Hemisphere vegetation 9000 and 6000 years ago warms Earth's surface by ~0.8° and 0.7°C, respectively, producing a better match with proxy-based reconstructions. Our results suggest that vegetation change is critical for modeling Holocene temperature evolution and highlight its role in driving a mid-Holocene temperature maximum.