Nature-based solutions (NBS) are valuable instruments for climate adaptation and resilience. Existing research on urban NBS barriers focuses mostly on structural and technical elements, while co-creation and local knowledge are regularly cited as critical for successful implementation. Even when barriers are easy to identify, a divide between ambition and reality generates procedural and knowledge gaps. This paper addresses this challenge through a case study of the Horizon Europe project URBREATH. Narrative inquiry is used to reveal invisible aspects of NBS implementation as experienced by city officials from Madrid, Cluj-Napoca, Leuven, and Tallinn. Drawing on storytelling workshops with city representatives and the authors’ participatory observation as project members, the paper shows that urban NBS are not only technical solutions, but also socio-cultural elements narrated through affective processes. We ask: what do city officials’ stories of difficult implementation moments reveal? Collected narratives show the personal commitment required to deliver urban nature-based solutions. Stories reveal that, in these cases, project managers absorbed institutional gaps informally, community participation was unevenly distributed, and hybrid NBS objects did not fit existing departmental categories. In navigating these barriers, narrative work itself operates as a form of governance practice. Narrowing this procedural and knowledge gap, we conclude, requires attention to affective and relational labour alongside procedural fixes.