Nature-based solutions (NbS) are recognized as effective tools for mitigating urbanization’s effects, enhancing environmental quality, promoting human well-being, and supporting economic development. When carefully planned, NbS present elements of green infrastructure (GI), essential for the sustainable functioning of cities. Since 2013, the European Union countries have launched a GI Strategy and a Biodiversity Strategy. As part of them, many cities such as Paris, London, Barcelona, Kalisz, etc. have developed specific technical guidelines for implementing NbS, including vertical greenery systems (VGS). In Serbia, urban planning has recently started to focus on GI, but further developments are needed. To contribute to this discourse, we reviewed the scientific literature to present VGS genesis in Belgrade and analyzed how the current “Plan of the General Regulation for the Green Areas System in Belgrade” from 2019 (2019 PGRGASB) presents VGS. Afterward, through field research, we examined six VGS case studies in public open spaces in Belgrade. This was followed by an international expert workshop to critically evaluate the VGS planning and design proposed by the 2019 PGRGASB. Recommendations were formulated for enhancing VGS planning and design, relevant not only to Serbia but also to other South-East European countries.