This paper aims to benchmark performance of combined solid waste management (SWM) and recycling systems in major cities of East Africa. The Wasteaware indicators are used to present a detailed systems analysis for Kigali in Rwanda, including a mass flow diagram; comparative data are taken from the Wasteaware database for Dar es Salaam, Tanzania, Kampala, Uganda, Nairobi, Kenya, and also for neighboring Maputo, Mozambique. The stand-out result is the relatively high collection coverage achieved, in Maputo with extensive international technical assistance, and in Kigali using its own local resources. In both cases, governance factors are key. Kigali uses a public–private partnership, with exclusive franchises in 35 sectors being tendered every three years; households pay an affordable fee depending on their ability to pay (the service is free to the poorest category); and 95% fee collection rates are achieved, partly through co-collection with charges for local security patrols, which is a service people value highly given the recent history of the country. Another key priority to improve SWM across East Africa is to eliminate open dumping – only Kampala currently has an engineered disposal site. Recycling rates also need to be increased – only Nairobi currently has a good baseline to build on (30%). Common weaknesses include a lack of segregation at source, of institutional capacity, and of available and reliable waste data.