University leaders play crucial roles in steering and fostering change within higher education institutions (HEIs). Drawing upon the complexity leadership theory (CLT) and organizational trust, we investigate how university leaders trusting staff with responsibilities tied to digital change contributed to an institutional culture of innovation. Through 68 interviews with staff members working in 8 European study programs, we found that leaders exhibited trust by creating flat hierarchies, sharing decision-making, and ensuring a safe space for experimentation with educational technologies (EdTech). This led to staff being intrinsically motivated to engage with technology and innovate with new formats. We also found that university leaders sometimes used 'trust' to justify allocating the responsibilities of digital change to the shoulders of staff without providing support such as infrastructure, funding, and guidance. This contributed to demotivation and stifled innovation. This study highlights the importance of university leaders trusting and empowering their staff members' creative processes with technology and supporting innovation within higher education.