Our understanding of the impact of climate-driven environmental change on prehistoric human populations is hampered by the scarcity of continuous paleoenvironmental records in the vicinity of archaeological sites. Here we compare a continuous paleoclimatic record of the last 20 ka before present from the Chew Bahir basin, southwest Ethiopia, with the available archaeological record of human presence in the region. The correlation of this record with orbitally-driven insolation variations suggests a complex nonlinear response of the environment to climate forcing, reflected in several long-term and short-term transitions between wet and dry conditions, resulting in abrupt changes between favorable and unfavorable living conditions for humans. Correlating the archaeological record in the surrounding region of the Chew Bahir basin, presumably including montane and lake-marginal refugia for human populations, with our climate record suggests a complex interplay between humans and their environment during the last 20 ka. The result may contribute to our understanding of how a dynamic environment may have impacted the adaptation and dispersal of early humans in eastern Africa.