Lake Victoria is a crucial ecosystem for over 25 million people in Kenya, Uganda, Tanzania, Rwanda and Burundi who live in the basin, and for the greater Nile river system downstream of the lake. Ecosystem management in the Lake Victoria basin has been highly extractive for most of the last 60 years, with the 1990s a period of marked decline in food production, economic contraction, rising poverty, increased burden of human disease, and more frequent floods. Lake Victoria itself is becoming eutrophic, with related problems of species extinctions and invasive species. There is evidence of poverty-environment traps: some households and areas appear to be caught in vicious cycles of low income, low investment in soil management, declines in soil fertility, and soil loss, while other households and areas are able to achieve higher incomes and investments, maintain soil fertility, and conserve soil on their farms. Concepts and approaches from the Millenium Ecosystem Assessment (MA) were applied in a study of ecosystem service tradeoffs, synergies and traps in two of the river basins that flow into Lake Victoria from Kenya (Yala and Nyando). Hydrologic units are the main geographic unit used in the analysis, with predictions of sediment yield serving as the main measure of regulating services. Provisioning services are evaluated through a spatially disaggregated analysis of agricultural production, yield and area that combines spatial data from aerial photographs with division-level price and yield estimates. The results illustrate considerable year-to-year variation in land use, agricultural production and sediment yield in the two basins. While overall production appears to be relatively stable at the basin level, there have been shifts in the geographic locus of production toward the upper parts of both basins. A spatial overlay of production and sediment yield indicates that different parts of the basins exhibit tradeoffs, synergies and traps. Results from this study have multiple uses in rural planning, agricultural investment, and watershed management. The results also suggest that the poverty traps conceptual framework may help to enrich the interpretative content of the MA approach.