The relationship between the mean state of the Pacific Ocean and El Niño Southern Oscillation (ENSO) and its variability through time is inadequately understood, especially on longer timescales. Several studies have indicated that the mid-Holocene (6,000 years before present) was characterized by stronger east-west temperature contrast and lower ENSO variability relative to the present day. While climate models show a reduction in ENSO variability, they underestimate this reduction compared to many paleoclimate reconstructions. Further, the drivers behind these changes remain unclear. In this work, we use five global climate models to show that incorporating vegetation changes over northern Africa during the mid-Holocene are vital to capturing global circulation changes. Greening the Sahara alters the Walker Circulation, enhancing zonal temperature and pressure gradients in the equatorial Pacific and driving it to a La Niña-like state. Incorporating Green Sahara boundary conditions leads to reductions in interannual variability in all Niño index regions relative to orbital and GHG changes, with reductions of up to 18% in the Niño3.4 region. Our work highlights the importance of the Atlantic influence on ENSO and provides paleoclimatic evidence for this synergistic teleconnection.