The public sector is becoming increasingly complex. As complexity leadership theory has been formulated in order to understand leadership in such a context, it thus seems appropriate that it should inform public leadership research. However, the applicability of complexity leadership theory and the concomitant adaptive leadership practices have thus far been underexplored empirically in a public sector context. To address this omission, this article uses a qualitative case study to exemplify how adaptive leadership practices may manifest themselves in a public sector context. The article’s findings indicate that adaptive leadership practices that reduce, rather than induce, tension within the dynamics of actors’ interactions may be a more viable route to handle challenges within a public sector context. Future research could beneficially pay greater attention to the public sector context when studying how adaptive leadership practices might manifest themselves in public sector organizations, as well as when assessing the merits of complexity leadership theory in informing public leadership.