Poor waste flows management in East African cities has become an environmental and public health concerns to the city authorities and the general public. We assessed the environmental impacts of waste recycling in Kampala City, for four designed waste management scenarios, namely: (1) Scenario S1 representing the current status quo, (2) Scenario S2 maximizing landfill, (3) Scenario S3 combining composting, resource recovery, landfill and sewerage, and (4) Scenario S4 integrating anaerobic digestion, resource recovery, landfill and sewerage. These scenarios are quantitatively assessed for environmental impacts of global warming, acidification, nutrient enrichment, photochemical ozone formation, water pollution and resource conservation. Sensitivity analyses are performed on the robustness for the ranking of the scenarios. Scenario S4 integrating anaerobic digestion, resource recovery, landfill and sewerage performs best for all environmental impact categories. Sensitivity analysis shows that this assessment result is robust. Therefore, integrating waste recycling into the formal waste management system for Kampala would considerably reduce the environmental impacts of waste flows. Also, considering the similarities in municipal solid waste compositions, sanitation systems and settlement patterns among the large cities in East Africa, assimilating waste recycling into the formal waste management systems for these cities would results in minimal environmental impacts for their waste flows.