Widely distributed proxy records indicate that the Medieval Climate Anomaly (MCA; ~900–1350 AD) was characterized by coherent shifts in large-scale Northern Hemisphere atmospheric circulation patterns. Although cooler sea surface temperatures in the central and eastern equatorial Pacific can explain some aspects of medieval circulation changes, they are not sufficient to account for other notable features, including widespread aridity through the Eurasian sub-tropics, stronger winter westerlies across the North Atlantic and Western Europe, and shifts in monsoon rainfall patterns across Africa and South Asia. We present results from a full-physics coupled climate model showing that a slight warming of the tropical Indian and western Pacific Oceans relative to the other tropical ocean basins can induce a broad range of the medieval circulation and climate changes indicated by proxy data, including many of those not explained by a cooler tropical Pacific alone. Important aspects of the results resemble those from previous simulations examining the climatic response to the rapid Indian Ocean warming during the late twentieth century, and to results from climate warming simulations—especially in indicating an expansion of the Northern Hemisphere Hadley circulation. Notably, the pattern of tropical Indo-Pacific sea surface temperature (SST) change responsible for producing the proxy-model similarity in our results agrees well with MCA-LIA SST differences obtained in a recent proxy-based climate field reconstruction. Though much remains unclear, our results indicate that the MCA was characterized by an enhanced zonal Indo-Pacific SST gradient with resulting changes in Northern Hemisphere tropical and extra-tropical circulation patterns and hydroclimate regimes, linkages that may explain the coherent regional climate shifts indicated by proxy records from across the planet. The findings provide new perspectives on the nature and possible causes of the MCA—a remarkable, yet incompletely understood episode of Late Holocene climatic change.