This paper focuses on the development of a participatory planning approach for local energy sustainability. The characteristics of a complex problem were reviewed to establish that the problem of sustainable energy at a local government level is complex. In order to better manage complex problems, the literature shows that soft operational research or problem-structuring methods need to be applied, and hence these methods were used as a starting point for developing a participatory planning approach. The requirements for a planning approach were elicited, namely that the approach must be participative and inclusive, holistic, simple and transparent. In addition, the approach must include the identification and assessment of risks as part of the deliberation process, the development of a realistic action plan must be attainable at the end of the stakeholder engagement, the approach must be dynamic, and should be formalised with clear institutional arrangements. A novel participatory approach, namely EDAS—to Explore, Design and Act for Sustainability—was then developed, applied, and evaluated as part of a case study with a local municipality in the Western Cape Province of South Africa. The insights are relevant not only for local governments, but for any institution on a journey towards sustainability.