Stereocaulon vesuvianum is among the most widespread and abundant fruticose lichens in montane Britain. While undertaking fieldwork in North Wales in 2006, we encountered large populations of S. vesuvianum without cephalodia and covered by an alga-rich biofilm. By contrast, populations in western Scotland had abundant cephalodia and largely lacked algal biofilms. We hypothesized that these morphological changes might be caused by nitrogen enrichment. Recent fieldwork has shown that cephalodial abundance in S. vesuvianum is highly correlated with modelled N deposition and that cephalodia are either rare or absent in regions of Britain currently experiencing moderate to high rates of N deposition. Examination of archival herbarium material revealed that S. vesuvianum collected from these regions between 1840-1920 were abundantly cephalodiate but that post 1940 the capacity to form cephalodia had been lost over much of England and Wales. Rates of nitrogenase activity in those cephalodia that form infrequently in polluted regions are similar to rates in background regions and biofilm-rich pseudopodetia that lack cephalodia have no detectable nitrogenase activity; hence cephalodial abundance is a good proxy for nitrogen-fixing capacity in this species. There is also a trend for S. vesuvianum in N-enriched regions to produce more abundant apothecia and more abundant and larger, plate-like phyllocladia. Variation in thallus chemistry in S. vesuvianum is consistent with loss of nitrogen-fixing capacity in N-enriched regions. At all sampling sites Parmelia saxatilis was collected in tandem with S. vesuvianum to provide a non-nitrogen-fixing reference species for comparative purposes and to facilitate estimation of nitrogen-fixing rates using 15N natural abundance data. However, our results suggest that N capture strategies might differ substantially between these two species invalidating the use of P. saxatilis as a reference species. The possible wider implications of N enrichment for biological nitrogen fixation are considered.