Many important hominid-bearing fossil localities in East Africa are in regions that are extremely hot and dry. Although humans are well adapted to such conditions, it has been inferred that East African environments were cooler or more wooded during the Pliocene and Pleistocene when this region was a central stage of human evolution. Here we show that the Turkana Basin, Kenya--today one of the hottest places on Earth--has been continually hot during the past 4 million years. The distribution of (13)C-(18)O bonds in paleosol carbonates indicates that soil temperatures during periods of carbonate formation were typically above 30 degrees C and often in excess of 35 degrees C. Similar soil temperatures are observed today in the Turkana Basin and reflect high air temperatures combined with solar heating of the soil surface. These results are specific to periods of soil carbonate formation, and we suggest that such periods composed a large fraction of integrated time in the Turkana Basin. If correct, this interpretation has implications for human thermophysiology and implies a long-standing human association with marginal environments.