Since the start of the Holocene, temperatures in the Arctic have steadily declined. This has been accredited to the orbitally forced decrease in summer insolation reconstructed over the same period. However, here we present climate modelling results from an Earth model of intermediate complexity (EMIC) that indicate that 17-40% of the cooling in the Arctic, over the period 9-0 ka, was a direct result of the desertification that occurred in the Sahara after the termination of the African Humid Period. We have performed a suite of sensitivity experiments to analyse the impact of different combinations of forcings, including various vegetation covers in the Sahara. Our simulations suggest that over the course of the Holocene, a strong increase in surface albedo in the Sahara as a result of desertification led to a regional increase in surface pressure, a weakening of the trade winds, the westerlies and the polar easterlies, which in turn reduced the meridional heat transported by the atmosphere to the Arctic. We conclude that during interglacials, the climate of the Northern Hemisphere is sensitive to changes in Sahara vegetation type.