This chapter considers learning, change and innovation in a public sector where the certainties of ‘New Public Management’ (NPM) have been replaced by uncertainty and flux. In this setting, policy actors may resort either to innovation or retrenchment. New solutions to policy problems may be generated or actors may revert to foundational approaches. This impacts upon practice as stakeholders search for meaning and engage in sense-making. Drawing from the authors’ research within the UK public sector, this theoretical paper argues that rapid change and the failure of old solutions (for instance, to the global financial crisis) do not necessarily generate positive innovation. There may indeed be a retreat to previous failed responses, with entrenched learning producing negative results. The chapter concludes that innovation requires the core component of creativity if it is to be of value. As the modernist conception of gradual mastery of the world has fallen away, different theoretical tools are needed in understanding this changed policy environment. It is suggested that established governance and network theories are of limited assistance. It is more useful to adopt an anti-foundationalist position, using sense-making perspectives informed by both Weberian and critical approaches while avoiding grand meta-narrative.