Various sets of skills for dealing with sustainability and the complexity of the modern world have been put forward by different actors in the field of Education for Sustainable Development (ESD). In connection with these skills, pedagogical methods such as lifelong learning, social learning, problem-based learning, dialogue education, and empowerment for ESD have been discussed. This paper looks at how these theories and methods can be put into practice by examining a real-world example of a sustainability master’s program at Blekinge Institute of Technology (BTH) in Sweden. In 2004, BTH launched the international transdisciplinary master’s program Strategic Leadership towards Sustainability, which aims to develop leaders who will be able to address the ever-increasing sustainability challenge. The program combines a robust scientific framework for planning and decision making toward sustainability, with the leadership skills needed to energize large-scale societal change. In 2009, the Engineering Education for Sustainable Development (EESD) observatory awarded BTH the ranking of No. 1 in Sweden and third in Europe for demonstrating success in EESD. This paper describes the specific pedagogical approaches and design elements that were implemented to train and develop the skills and expertise surrounding leadership for sustainable development. It further presents and analyzes survey data taken from program alumni reflecting on the success of the program. The results of the survey clearly show that while there is room for improvement, overall the program design is extremely successful in equipping its graduates with the skills necessary to address the sustainability challenge. Finally, the authors offer reflections on the lessons learned after six years of continual improvements.