Many lichens have been used as bioindicators for air pollutants such as $SO_2$. The first ecological study on lichens in Korea was conducted in 1975 by Kim and Lee, disclosing that areas adjacent to the center of Seoul were lichen deserts. Air quality in Seoul has improved significantly since the 1980s. However, the distribution of lichen species has not been reevaluated since then. We examined the spatial and temporal pattern of lichen distribution by selecting six (inner city green [ICG] and four (outer city green [OCG]) sites, based on the distance from the city center of Seoul and the land use pattern. The change in lichen distribution was related to yearly mean concentrations of $SO_2$, $NO_2$, and $O_3$ for the years 1980-2009. Four and 13 lichen species were found in ICGs and OCGs, respectively. Although mean sample numbers per species were much higher in the former, species richness tended to increase with distance from the city center. Since 1980, $SO_2$ has declined drastically to < 0.01 ppm in both ICGs and OCGs, indicating that $SO_2$ is no longer a limiting factor for lichen establishment and growth. In contrast, $NO_2$ has increased steadily for 20 years (1989-2009) and a considerable proportion of lichen species in both ICGs and OCGs are known as nitrophilic or pollution-tolerant species. Appearance of nitrophiles in both ICGs and OCGs and the dominance of a few lichen species in ICGs may reflect the effects of the increase in $NO_2$. In contrast to $SO_2$ and $NO_2$, $O_3$ was higher in OCGs, but it was difficult to identify a causal relationship between $O_3$ and lichen distribution.