A study of governance and urban waste must examine not only the formal structures of government but also the informal structures created by the society, such as community-based institutions, associations, and organizations; their relationships; and the relationship between the formal and informal structures for collection, transportation, and disposal of waste. It is evident that municipalities in developing countries and particularly so in East Africa, typically lack the financial resources and skills needed to cope with the crisis of solid waste management. This raises the important issue of how to deliver quality service in the face of the financial and skill constraints of the public sector. Comparing governance arrangements that incorporate non-state actors in three urban authorities Kisumu (Kenya); Jinja (Uganda) and Mwanza (Tanzania) in East Africa, allowed this study to describe and appraise performance of these non-state actors in solid waste management at the municipal level with an aim of recommending policy options. Issues addressed are legitimacy and influence on decision-making; relations and alliances and the payment systems. Theoretical arguments of neo-developmental states verses network states in governance, guided the discussion. Household surveys; interviews and document analysis were the method used to gather data, SPSS-PASWStatistics_17.0 is used to make analysis of the quantitative data while coding is helpful in handling the qualitative data. The study concluded that a mixed modern approach in governance is needed to achieve sustainability. This would bring together the best features of central system of governance and the decentralized system to obtain an optimum mix.