Urbanisation has resulted in significant environmental challenges, particularly the phenomenon of urban overheating, with a significant increase in temperatures in urban environments. To tackle the adverse impact of urban overheating, the implementation of green infrastructure (GI) has been considered particularly effective. Although there are various benefits of GI for sustainable urban management, its widespread implementation faces numerous challenges. To effectively scale up the deployment of GI, it is crucial to develop political and institutional frameworks that are both responsive and adaptable to the evolving complexities inherent in human–nature interactions. The barriers to implementation are not merely technical but also embedded in organisational norms, social practices, and governance systems, which makes them particularly difficult to overcome. This paper identifies five key categories of barriers: technical limitations, financial impediments, regulatory constraints, weak political leadership, and governance and coordination challenges. Through a targeted literature review and a detailed case study of Melbourne, the paper explores the city’s primary greening initiatives and examines how these barriers have influenced implementation. By linking specific policy responses to each barrier, this study provides new insights into the institutional and policy dynamics affecting GI adoption. The findings offer lessons for other cities seeking to better implement nature-based solutions through integrated and scalable GI strategies.