Open-air archaeological sites record only a small fraction of the behavioral traces of mobile forager populations. Whereas caves and rockshelters were often occupied at least in part for protection from the elements, the reasons why human foragers occupied other places on the landscape (however briefly) are varied and not always readily recoverable. We develop a framework for interpreting human use of the landscape and modeling occupation of open-air sites using the archaeological and paleoenvironmental record of Middle Stone Age (MSA) sites from Rusinga and Mfangano Islands, located near the eastern margin of Lake Victoria. Paleoenvironmental reconstructions using fossil faunas suggest an arid grassland setting unlike the present. Paleoecological modeling of the habitats of extant and extinct bovids, combined with GIS-based reconstructions of lake level change, indicate that human occupation of these sites coincided with substantial declines in the level of Lake Victoria. During this time, both Rusinga and Mfangano would have been connected to the mainland and represented local topographic highs within an extensive grassland. Geological, ecological, and ethnobotanical observations suggest that these topographic high points would likely have been important sources of stone raw material, fresh water, and a variety of plant resources for food, fuel, and other purposes. In contrast, the grassy lowland plains were probably exploited primarily as a source of large game, which included numerous species of large gregarious grazers, several of which may have followed now extinct migration routes.