A sequence of paleosols in the Solo Basin, Central Java, Indonesia, documents the local and regional environments present when Homo erectus spread through Southeast Asia during the early Pleistocene. The earliest human immigrants encountered a low-relief lake-margin landscape dominated by moist grasslands with open woodlands in the driest landscape positions. By 1.5 Ma, large streams filled the lake and the landscape became more riverine in nature, with riparian forests, savanna, and open woodland. Paleosol morphology and carbon isotope values of soil organic matter and pedogenic carbonates indicate a long-term shift toward regional drying or increased duration of the annual dry season through the early Pleistocene. This suggests that an annual dry season associated with monsoon conditions was an important aspect of the paleoclimate in which early humans spread from Africa to Southeast Asia.