East African landscapes today are the result of the cumulative effects of climate and land-use change over millennial timescales. In this review, we compile archaeological and palaeoenvironmental data from East Africa to document land-cover change, and environmental, subsistence and land-use transitions, over the past 6000 years. Throughout East Africa there have been a series of relatively rapid and high-magnitude environmental shifts characterised by changing hydrological budgets during the mid- to late Holocene. For example, pronounced environmental shifts that manifested as a marked change in the rainfall amount or seasonality and subsequent hydrological budget throughout East Africa occurred around 4000, 800 and 300 radiocarbon years before present (yr BP). The past 6000 years have also seen numerous shifts in human interactions with East African ecologies. From the mid-Holocene, land use has both diversified and increased exponentially, this has been associated with the arrival of new subsistence systems, crops, migrants and technologies, all giving rise to a sequence of significant phases of land-cover change. The first large-scale human influences began to occur around 4000 yr BP, associated with the introduction of domesticated livestock and the expansion of pastoral communities. The first widespread and intensive forest clearances were associated with the arrival of iron-using early farming communities around 2500 yr BP, particularly in productive and easily-cleared mid-altitudinal areas. Extensive and pervasive land-cover change has been associated with population growth, immigration and movement of people. The expansion of trading routes between the interior and the coast, starting around 1300 years ago and intensifying in the eighteenth and nineteenth centuries CE, was one such process. These caravan routes possibly acted as conduits for spreading New World crops such as maize (Zea mays), tobacco (Nicotiana spp.) and tomatoes (Solanum lycopersicum), although the processes and timings of their introductions remains poorly documented. The introduction of southeast Asian domesticates, especially banana (Musa spp.), rice (Oryza spp.), taro (Colocasia esculenta), and chicken (Gallus gallus), via transoceanic biological transfers around and across the Indian Ocean, from at least around 1300 yr BP, and potentially significantly earlier, also had profound social and ecological consequences across parts of the region.