Sustainable Development is recognized as one of the biggest societal challenges of the twenty-first century. Higher Education Institutions have the vision, the knowledge and the power to lead this transition, and to induce the changes towards this new paradigm. As a result, sustainability values need to be incorporated in Higher Education Institutions’ mission and practice. Although some successful case studies have been reported, there is a lack of consolidated methodologies to support an integrated and holistic implementation of sustainability, as well as to identify the opportunities associated with this process. The present research contributes to this literature by presenting the implementation of the sustainability vision of University of Minho (between 2009 and 2017), in a holistic and inclusive perspective, demonstrating the engagement and alignment of the Academic Community and the Rectorate. Based on the findings it is possible to derive some important lessons for the implementation of Sustainability Strategies in Higher Education Institutions. A mixed Bottom-up and Top-Down approach is seen as a key element for the successful change of the organizational culture. The implementation of sustainability policies that address all mission areas and the continuous monitoring and communication is crucial to demonstrate the commitment to all stakeholders. In addition, the integration of collaborative networks and the institutionalization of sustainable policies contribute to consolidate and strengthen the commitment with sustainability. The considered methodology and findings can significantly contribute to enrich the existent literature on reporting HEI sustainability practices, and to promote Sustainability Strategies in Higher Education Institutions, and other organizations, provided that their intrinsic nature is accounted for.