Learning analytics (LA) has demonstrated great potential in improving teaching quality, learning experience and administrative efficiency. However, the adoption of LA in higher education is often beset by challenges in areas such as resources, stakeholder buy-in, ethics and privacy. Addressing these challenges in a complex system requires agile leadership that is responsive to pressures in the environment and capable of managing conflicts. This paper examines LA adoption processes among 21 UK higher education institutions using complexity leadership theory as a framework. The data were collected from 23 interviews with institutional leaders and subsequently analysed using a thematic coding scheme. The results showed a number of prominent challenges associated with LA deployment, which lie in the inherent tensions between innovation and operation. These challenges require a new form of leadership to create and nurture an adaptive space in which innovations are supported and ultimately transformed into the mainstream operation of an institution. This paper argues that a complexity leadership model enables higher education to shift towards more fluid and dynamic approaches for LA adoption, thus ensuring its scalability and sustainability.