Purpose: Guided by paradox theory, the study aims to significantly advance Sustainability in Higher Education Institutions (SHEI) scholarship and inform change agents' (CAs) practices by uncovering the tensions underlying the challenges CAs face in embedding sustainability in their universities and learning about potential strategies to manage these tensions. Design/methodology/approach: The authors conducted a multi-step, mix-methods study including interviews (n = 15), an online survey (n = 36) and focus groups (n = 29) with CAs from 17 of Austria's 22 public universities. Participating CAs consisted of faculty, staff and administrators with leading roles in their Higher Education Institutions' sustainability change processes. Findings: Austrian SHEI CAs' responses revealed 15 tensions at and between the individual, organizational and system level addressing academic, organizational and external stakeholder engagement aspects. Six tensions were selected for more in-depth exploration including elaboration of management strategies, building on CAs' experiences. Results revealed examples of acceptance, separation and synthesis strategies. Research limitations/implications: Based on the exploratory nature of our study, the authors do not claim to have identified a comprehensive list of tensions underlying the challenges faced by SHEI CAs, nor of all potential management strategies. Practical implications: Although this study focused exclusively on Austrian SHEI CAs, the challenges they shared were consistent with those in the literature and, thus, insights should also support the CAs' efforts in other countries. Originality/value: This study offers novel perspectives on how to manage the challenges to SHEI. To the best of the authors' knowledge, it is the first to describe paradox theory-informed management strategies recommended by a heterogenous group of SHEI CAs to address the barriers they face in transforming their universities toward sustainability.