While CO2 emissions of cities are widely discussed, carbon storage in urban vegetation has been rarely empirically analyzed. Remotely sensed data offer considerable benefits for addressing this lack of information. The aim of this paper is to develop and apply an approach that combines airborne LiDAR and QuickBird to assess the carbon stored in urban trees of Berlin, Germany, and to identify differences between urban structure types. For a transect in the city, dendrometric parameters were first derived to estimate individual tree stem diameter and carbon storage with allometric equations. Field survey data were used for validation. Then, the individual tree carbon storage was aggregated at the level of urban structure types and the distribution of carbon storage was analysed. Finally, the results were extrapolated to the entire urban area. High accuracies of the detected tree locations were reached with 65.30% for all trees and 80.1% for dominant trees. The total carbon storage of the study area was 20,964.40 t (σ = 15,550.11 t). Its carbon density equaled 13.70 t/ha. A general center-to-periphery increase in carbon storage was identified along the transect. Our approach methods can be used by scientists and decision-makers to gain an empirical basis for the comparison of carbon storage capacities between cities and their subunits to develop adaption and mitigation strategies against climate change.