This study investigates a reciprocal partnership between two cities in Namibia and Sweden to deepen the understanding of challenges and learning outcomes in a project on education for sustainable development. Since 2008, two municipalities have developed a strong partnership via The Municipal Partnership Programme at the Swedish International Centre for Local Democracy. Municipal partnerships are results-oriented collaborations in joint projects on sustainability. The purpose is to describe how eight team members in the mutual South-North project, by addressing similar problems in different contexts, experienced challenges in the implementation of the project plan, solutions and learning processes. Semi-structured interviews were conducted at the end of the second project year. Transcripts and field notes were analysed using a phenomenographic approach and contextual analysis. Five main categories of description based on collective statements and three dimensions of learning were recognised in the research data. The analysis identifies strategies for critical knowledge formation and capability building to support mutual learning in South-North Municipal Partnerships. The concluding discussion spots the learning dimensions—how sharing experiences by justifying non-formal and transformational learning promotes organisations’ readiness for knowledge formation by conducting mutual global learning towards sustainable development goals.