Nature-based solutions (NBS) are essential for carbon-neutral cities, yet how to effectively allocate them remains a question. Carbon neutrality requires city-led climate action plans that incorporate both indirect and direct contributions of NBS. Here we assessed the carbon emissions mitigation potential of NBS in European cities, focusing particularly on commonly overlooked indirect pathways, for example, human behavioural interventions and resource savings. Assuming maximum theoretical implementation, NBS in the residential, transport and industrial sectors could reduce urban carbon emissions by up to 25%. Spatially prioritizing different types of NBS in 54 major European Union cities could reduce anthropogenic carbon emissions by on average 17.4%. Coupling NBS with other existing measures in Representative Concentration Pathway scenarios could reduce total carbon emissions by 57.3% in 2030, with both indirect pathways and sequestration. Our results indicate that carbon neutrality will be near for some pioneering cities by 2030, while three can achieve it completely.