Much remains unknown about the genetic status and population connectivity of high-elevation and high-latitude freshwater invertebrates, which often persist near snow and ice masses that are disappearing due to climate change. Here we report on the conservation genetics of the meltwater stonefly Lednia tumana (Ricker) of Montana, USA, a cold-water obligate species. We sequenced 1530 bp of mtDNA from 116 L. tumana individuals representing “historic” (>10 yr old) and 2010 populations. The dominant haplotype was common in both time periods, while the second-most-common haplotype was found only in historic samples, having been lost in the interim. The 2010 populations also showed reduced gene and nucleotide diversity and increased genetic isolation. We found lower genetic diversity in L. tumana compared to two other North American stonefly species, Amphinemura linda (Ricker) and Pteronarcys californica Newport. Our results imply small effective sizes, increased fragmentation, limited gene flow, and loss of genetic variation among contemporary L. tumana populations, which can lead to reduced adaptive capacity and increased extinction risk. This study reinforces concerns that ongoing glacier loss threatens the persistence of L. tumana, and provides baseline data and analysis of how future environmental change could impact populations of similar organisms.