Road traffic emits a cocktail of pollutants that can influence the vegetation and plant diversity in neighboring areas. However, the recovery potential of bryophytes after traffic abandonment is still little explored. In addition, the effects of the main pollutants of road verges, such as metals and salinity, on moss flora need to be investigated. In our study, we compared the moss richness and diversity in two closely related veteran tree allees of high conservation importance. The allees in Gryżów and Lubrza, Poland, were chosen because of their similarity in age, geographical location, type of surrounding areas, and tree species. The only difference was that the trees in Gryżów had not been exposed to direct road pollution for almost 30 years. The moss richness and diversity differed significantly between the sites. Altogether, 20 moss species were recorded on 229 trees, 17 species in Gryżów (abandoned road), and 13 in Lubrza (busy road). We found considerable differences between moss cover on the road-facing and opposite sides of tree trunks. In Lubrza, mosses on the road-facing side were very scarce. The moss cover in Gryżów was highly balanced between trunk sides as well as among trunk heights. Typical epiphytic species such as Bryum moravicum, Dicranoweisia cirrata, Leskea polycarpa, and Orthodicranum tauricum preferred the Gryżów tree stands, where they were present in numbers almost twice as high as that at Lubrza. The study shows that constructing a bypass road could be an effective conservation measure for veteran tree protection with their epiphytic moss flora.