No species of freshwater Nematomorpha have been described from Iceland, but they have been identified anecdotally. Recent surveys in Iceland using freshwater gastropods as biodiversity indicators resulted in the collection of adult free-living hairworms and their non-adult stages including cysts in snail paratenic hosts and juvenile worms in ground beetle definitive hosts. Additionally, specimens acquired from the Icelandic Institute of Natural History indicate nematomorphs are common in Iceland. A single specimen from the Faroe Islands National Museum represents a new species record. Our morphological and molecular characterization indicated all the samples belong to the species Gordionus wolterstorffii, a common nematomorph found throughout Europe. Also, we provide the first descriptions of the cyst stage for the genus Gordionus. Molecular phylogenetic analysis based on 10 species of Gordionus and one species of the closely related genus Parachordodes indicates that Gordionus is not monophyletic. Combining our morphological and phylogenetic investigations, we discuss the lack of clarity in diagnostic morphological characters and the need for additional global collections to clarify the taxonomy of Gordionus.