Lichens are highly sensitive to air pollution and are often absent from the central areas of major urban agglomerations (“lichen deserts”). We compared the cover of corticolous lichen species recorded on trees surveyed at 105 sampling stations in Québec City (Québec, Canada) in 1985 and 1986, to that found at the same locations in 2016. Total lichen cover increased at 80% of the sampling stations by an average of 86%, for all species and all stations combined. Candelaria concolor showed the greatest increase in cover (+91%). By contrast, the 3 most pollution sensitive species present, Evernia mesomorpha, Flavoparmelia caperata and Punctelia rudecta, showed the smallest increases. Nevertheless, F. caperata was detected at substantially more stations in 2016 (34) than during the study conducted in 1985 and 1986 (21), including in the more central urban areas. The lichen desert observed in the more urbanized parts of Québec City in 1985 and 1986 was no longer present in 2016. This increase in lichen cover is consistent with the marked decrease in sulphur dioxide levels recorded in Québec City since the early 1990s.