Many aspects of global change, including carbon dioxide emissions, have been attributed to urban areas. On the other hand, cities have been found to provide valuable ecosystem services such as carbon storage. The aim of this study is to estimate the above-ground carbon storage in trees in the central European city of Leipzig and produce spatially explicit carbon storage maps. We used stratified random sampling across 19 land cover classes using 190 sample plots to measure carbon storage. In addition, we derived canopy cover from color-infrared orthophotos using an object-oriented approach and Random Forest machine learning. Finally, we apply an error assessment method that includes sampling error, but also uncertainty stemming from allometric equations, and that so far has only been applied to rural forests. The total above ground carbon stock of Leipzig was estimated using both land cover and canopy cover, which was more laborious than just using land cover but reduced the standard error. Canopy cover was approximately 19% of the city area. Leipzig’s above-ground carbon storage was estimated to be 316,000 Mg C at 11 Mg C ha−1. The distribution of carbon storage across the city showed the highest values at intermediate urbanization levels. Carbon storage in the city of Leipzig was in the lower range compared to cities in Europe, Asia and the USA, and our results indicate that great care should be taken when transferring values between cities. We provide spatially explicit and detailed maps of above-ground storage that can contribute to ecosystem services assessments.