Warming climates are rapidly transforming lake ecosystems worldwide, but the breadth of changes in tropical lakes is poorly documented. Sustainable management of freshwater fisheries and biodiversity requires accounting for historical and ongoing stressors such as climate change and harvest intensity. This is problematic in tropical Africa, where records of ecosystem change are limited and local populations rely heavily on lakes for nutrition. Here, using a ∼1,500-y paleoecological record, we show that declines in fishery species and endemic molluscs began well before commercial fishing in Lake Tanganyika, Africa’s deepest and oldest lake. Paleoclimate and instrumental records demonstrate sustained warming in this lake during the last ∼150 y, which affects biota by strengthening and shallowing stratification of the water column. Reductions in lake mixing have depressed algal production and shrunk the oxygenated benthic habitat by 38% in our study areas, yielding fish and mollusc declines. Late-20th century fish fossil abundances at two of three sites were lower than at any other time in the last millennium and fell in concert with reduced diatom abundance and warming water. A negative correlation between lake temperature and fish and mollusc fossils over the last ∼500 y indicates that climate warming and intensifying stratification have almost certainly reduced potential fishery production, helping to explain ongoing declines in fish catches. Long-term declines of both benthic and pelagic species underscore the urgency of strategic efforts to sustain Lake Tanganyika’s extraordinary biodiversity and ecosystem services.