The evolution of the El Nino-Southern Oscillation (ENSO) during the Holocene remains uncertain. In particular, a host of new paleoclimate records suggest that ENSO internal variability or other external forcings may have dwarfed the fairly modest ENSO response to precessional insolation changes simulated in climate models. Here, using fully coupled ocean-atmosphere model simulations, we show that accounting for a vegetated and less dusty Sahara during the mid-Holocene relative to preindustrial climate can reduce ENSO variability by 25%, more than twice the decrease obtained using orbital forcing alone. We identify changes in tropical Atlantic mean state and variability caused by the momentous strengthening of the West Africa Monsoon (WAM) as critical factors in amplifying ENSO's response to insolation forcing through changes in the Walker circulation. Our results thus suggest that potential changes in the WAM due to anthropogenic warming may influence ENSO variability in the future as well.