Partnerships as enshrined in policies are vital for achieving sustainable cities under the Sustainable Development Goals (SDGs). Indeed the SDGs recognize the importance of partnerships in solid waste management (SWM) as a way of developing workable and reliable waste management systems. SWM in Nairobi city continues to be a great challenge, and poor practices threaten environmental and public health. Ineffective waste management in Nairobi city has been linked to inefficient policy implementation and enforcement by different stakeholders. To effectively address the challenge of sustainable waste management in Nairobi city, amalgamation of strategies amongst several segments, including stakeholders, private and public sectors (formal and informal), non-governmental organizations and communities, is important, through partnerships to implement improved policies, in terms of capacity, financial prudence, and technical and institutional factors. The paper seeks to analyse existing policy framework on SWM and its effectiveness in addressing SWM in Nairobi city. The study is based on a descriptive research design which involved interrogating the stakeholders included in the implementation of the policy frameworks in place. Data were acquired through semi-structured questionnaires administered to 385 respondents and interviews with 10 key informants. The theoretical framework is based on institutional theory and capacity building theories that expound the gaps in policy implementation and the role of partnerships. Policies in SWM should be interlinked for sustainable cities.