Service learning is a pedagogical approach that steps outside of the traditional classroom to enable learning experiences to occur within the community. Within formal education, service learning typically features active participation in structured experiences that are embedded within units of study. Increasing recognition of the value of service learning can be seen by the integration of service learning projects into university curricula in diverse areas such as public health, teacher training and local economic transformation, and recently music technology and music education. In recent years, the service learning approach has also been recognised not just for its benefits for learning and teaching within the university context, but also for its ability to contribute towards social change agendas and even widespread institutional and political reform. Whilst the value of service learning opportunities has long been aligned to student engagement, global citizenship and employability, the rhetoric can be far removed from the reality of organising such activities within universities. Particular challenges include academic workload and priorities within the context of a research- and output- driven environment; student focus on summative assessment, driven largely by competing priorities of work and study; and institutional constraints including funding and risk management. To add to the complexity, this project adopted a 'critical service learning' framework by moving beyond traditional service learning approaches to acknowledge both the complex and multi-directional relationships involved in such projects together with the objective of building more culturally appropriate relationships between students, Indigenous communities and universities more generally. In this paper we share the team's experiences and the strategies used to overcome some of the key challenges at each institution. By doing so we hope to prompt discussion of best practice and, at the same time, to think strategically about the role of service learning projects within the context of higher education reform.