Cities throughout the world are advocating highly promoted tree plantings as a climate change mitigation measure. Assessing the carbon offsets associated with urban trees relative to other climate change policies is vital for sustainable development, planning, and solving environmental and socio-economic problems, but is difficult in developing countries. We estimated and assessed carbon dioxide (CO2) storage, sequestration, and emission offsets by public trees in the Medellin Metropolitan Area, Colombia, as a viable Nature-Based Solution for the Neotropics. While previous studies have discussed nature-based solutions and explored urban tree carbon dynamics in high income countries, few have been conducted in tropical cities in low-middle income countries, particularly within South America. We used a public tree inventory for the Metropolitan Area of the Aburrá Valley and an available urban forest functional model, i-Tree Streets, calibrated for Colombia’s context. We found that CO2 offsets from public trees were not as effective as cable cars or landfills. However, if available planting spaces are considered, carbon offsets become more competitive with cable cars and other air quality and socio-economic co-benefits are also provided. The use of carbon estimation models and the development of relevant carbon accounting protocols in Neotropical cities are also discussed. Our nature-based solution approach can be used to better guide management of urban forests to mitigate climate change and carbon offset accounting in tropical cities lacking available information.