This study explores leadership in higher education institutions in Oman where education for sustainability issues are a high priority. The Vice-chancellor of the premier university Sultan Qaboos University, Qaboos Sultanate of Oman, and his four senior management team members answer the following question: What are the concrete steps which have been undertaken in order to allow the university to integrate sustainability in its: (a) curricula; (b) research; (c) practical projects; and (d) regional and national development endeavours? The views of these senior leaders carry larger national and international implications for the promotion of sustainability in Oman. They define their leadership as articulating a desire to bring about educational change and to prepare in practice for an explicit paradigm shift towards sustainability throughout the university and the country as well. Internationalization of the university is considered to be an important part of its sustainability strategy.