Anthropogenic climate change is predicted to severely impact the global hydrological cycle1, particularly in tropical regions where agriculture-based economies depend on monsoon rainfall2. In the Horn of Africa, more frequent drought conditions in recent decades3,4 contrast with climate models projecting precipitation to increase with rising temperature5. Here we use organic geochemical climate-proxy data from the sediment record of Lake Chala (Kenya and Tanzania) to probe the stability of the link between hydroclimate and temperature over approximately the past 75,000 years, hence encompassing a sufficiently wide range of temperatures to test the 'dry gets drier, wet gets wetter' paradigm6 of anthropogenic climate change in the time domain. We show that the positive relationship between effective moisture and temperature in easternmost Africa during the cooler last glacial period shifted to negative around the onset of the Holocene 11,700 years ago, when the atmospheric carbon dioxide concentration exceeded 250 parts per million and mean annual temperature approached modern-day values. Thus, at that time, the budget between monsoonal precipitation and continental evaporation7 crossed a tipping point such that the positive influence of temperature on evaporation became greater than its positive influence on precipitation. Our results imply that under continued anthropogenic warming, the Horn of Africa will probably experience further drying, and they highlight the need for improved simulation of both dynamic and thermodynamic processes in the tropical hydrological cycle.