Understanding the long-term dynamics of urban vegetation is essential in determining trends in the provision of key resources for biodiversity and ecosystem services and improving their management. Such studies are, however, extremely scarce due to the lack of suitable historical data. We use repeat historical photographs from the 1900s, 1950s, and 2010 to assess general trends in the quantity and size distributions of the tree stock in urban Sheffield and resultant aboveground carbon storage. Total tree numbers declined by a third from the 1900s to the 1950s, but increased by approximately 50% from the 1900s–2010, and by 100% from the 1950s–2010. Aboveground carbon storage in urban tree stocks had doubled by 2010 from the levels present in the 1900s and 1950s. The initial decrease occurred at a time when national and regional tree stocks were static and are likely to be driven by rebuilding following bombing of the urban area during the Second World War and by urban expansion. In 2010, trees greater than 10 m in height comprised just 8% of those present. The increases in total tree numbers are thus largely driven by smaller trees and are likely to be associated with urban tree planting programmes. Changes in tree stocks were not constant across the urban area but varied with the current intensity of urbanization. Increases from 1900 to 2010 in total tree stocks, and smaller sized trees, tended to be greatest in the most intensely urbanized areas. In contrast, the increases in the largest trees were more marked in areas with the most green space. These findings emphasize the importance of preserving larger fragments of urban green space to protect the oldest and largest trees that contribute disproportionately to carbon storage and other ecosystem services. Maintaining positive trends in urban tree stocks and associated ecosystem service provision will require continued investment in urban tree planting programmes in combination with additional measures, such as revisions to tree preservation orders, to increase the retention of such trees as they mature.