With the actual increasing interest for urban soils, the evaluation of soil contamination by trace elements and the dynamics of this contamination appear mandatory to preserve plant and thereby human health. Street trees and the associated soil placed in pits located nearby roads could represent convenient indicators of urban and vehicle traffic influences on soils and plants. However, data on these soils remain scarce, many studies investigating park soils rather than street tree soils. Furthermore, trace elements could be one of the main factors causing the observed urban tree decline, while practitioners more and more question the possible reuse of these soils after the death of trees as well as tree litter collected in the streets. We evaluated the contamination in anthropogenic trace elements (TE), namely Zn, Pb, and Cd, of street trees (Tilia tomentosa) and their soils distributed all over Paris (France). Street tree soils are imported from rural areas at the plantation of each new tree so that tree age corresponds to the time of residence of the soil within an urban environment allowing the evaluation of temporal trends on TE concentration in soils and trees. The TE concentration revealed an important soil pollution, especially for the older soils (mean age of 80 years old). The consideration of the residence time of trees and soils in an urban environment evidenced an accumulation of Zn and Pb (ca. 4.5 mg kg−1 year−1 and 4 mg kg−1 year−1 for Zn and Pb, respectively). However, leaf concentrations in TE were low and indicate that soil-root transfer was not significant compared to the contamination by atmospheric deposition. These results underlined the necessity to deepen the evaluation of the recycling of urban soils or plants submitted to urban contamination.