Pseudevernia furfuracea L. (Zopf), Peltigera praetextata (Flrke ex Sommerf.) Zopf, Lobaria pulmonaria (L.) Hoffm., and Usnea longissima Ach. lichen species were used as bioindicators to assess the genotoxicity of air pollutants. In the present study, we examined significant environmetal pollutants and investigate how changes may lead to damage in DNA structure using RAPD markers. In the study area (Erzurum, Turkey), poor-quality lignite, which generates a large amount of sulfur dioxide, nitrogen oxides, and particle matter, is used for domestic heating, and vehicles also contribute to air pollution. Control lichen samples were collected far from large urban and industrial settlements and transplanted to four polluted sites for 4, 8, or 12 months. The total soluble protein content of the examined four lichen species did not significantly change with exposure time (P < 0.05). The four lichen samples exposed to the pollutants for 8 months had the highest ratio of DNA changes. The ratio of band differences in P. praetextata was higher than that in the other three lichen species, possibly because it has broad leaves that accumulated more pollutants. The average incidences of polymorphism were 64.14, 54.58, 65.76, and 43.06% for P. furfuracea, P. praetextata, L. pulmonaria, and U. longissima, respectively. The genomic template stability (GTS) significantly decreased following exposure to pollutants. GTS ratios revealed that the highest value (98.36%) belonged to U. longissima samples from Site 1 (10 m) after 4 months of exposure, and the lowest values belonged to P. praetextata (73.58%) from Site 3 (100 m) after 8 months of exposure. Based on our findings, we recommend the use of P. praetextata as an indicator of genotoxicity.