Research investigating how urban greenery contributes toward carbon sequestration and storage (CSS) is mushrooming, and evidence-based design, management, and planning approaches are increasingly guiding the implementation of carbon-oriented nature-based solutions (NBS) in cities. However, the long-term success of NBS will largely depend on their social acceptability to residents, which in-turn is informed by their perceptions of the environmental issues at stake. In this study, we investigate residents’ perceptions of CSS in urban greenery and examine its influence on social acceptability of carbon-oriented NBS. We administered a survey containing nine hypothetical carbon-oriented NBS policies, and open-ended descriptions of the perceptions of CSS in urban greenery to 1,600 adult residents in Helsinki, Finland. Findings show that residents’ perceptions of CSS are primarily built on ecological dimensions (i.e., ecology of carbon and the carbon cycling in natural and semi-natural ecosystems) rather than socio-political ones (i.e., how humans, social, and political systems influence carbon cycling and dynamics in urban greenery). This finding shows an informational and perceptual gap among the public on how to design, manage, and plan urban greenery for CSS. We observed that females and those with higher levels of education and access to forest and natural areas tended to be more comfortable and familiar with CSS and believed urban greenery was effective in CSS. Lastly, we observed that socio-political and ineffectiveness CSS perceptual dimensions were more strongly related to social acceptability of carbon-oriented NBS. We conclude by discussing how public perceptions of CSS can enhance the social acceptance of carbon-oriented NBS, and we put forward strategies to integrate transformative learning about these NBS into urban greenery.