Despite promoting science-informed innovations in the form of Nature-based Solutions (NBS) for urban problems (e.g. flooding, unhealthy lifestyles) that are cheaper and more effective than traditional solutions (e.g. covering waterways, prescribing medicines), and have better climate and environmental outcomes, policy makers and key stakeholders have been slow to implement them. We argue that this is because the instrumental / technical rational view of policy making is still dominant in NBS—which assumes that (scientific) knowledge flows in a linear way from experts to rational decision makers who use it to make ‘better’ decisions and policies (see e.g. Jordan and Russel 2014; Weiss 1979). In practice, processes of policy- and decision-making are much more complex, involving multiple actors and types of information sources, and are influenced by external forces and events, including economic factors, the media and public opinion. Through comparative analysis of engagement with policy makers and stakeholders in three European urban case studies, we find political learning (including learning about the feasibility of policy proposals in a given context, negotiating within these constraints and appealing to political decision makers) to be key to successful NBS policy implementation, innovation and change. Political learning leading to policy change here also involve policy advocacy, coalition building and strategic knowledge utilisation—where knowledge is used tactically by different actors in particular sectors / venues of decision making (see Jordan and Russel 2014; Weiss 1979; Dunlop and Radaelli 2012). This paper also highlights characteristics and impacts of the shadow of hierarchy (see Dunlop and Radaelli 2012; Börzel 2010; Börzel and Risse 2010) on political learning and policy making in the different case studies.