The Holarctic diving beetle genus Graphoderus (Dytiscinae, Aciliini) contains relatively few and well-known species but these may still be difficult to identify based on external characters. A taxonomic problem in the eastern Palearctic was discovered that relates to the Palearctic Graphoderus zonatus (Hoppe, 1795) and the Nearctic Graphoderus perplexus Sharp, 1882. Based on qualitative and quantitative characters, especially on male genitalia which have been poorly studied in the past, it is shown that eastern Palearctic specimens identified by previous authors as either of the two species in fact belongs to a third species. The synonymized name Graphoderus elatus Sharp, 1882, is reinstated as a valid species (stat. n.) and a lectotype is designated from the mixed syntype series. The male genitalia of all known Graphoderus species have been examined and an illustrated identification key to the genus is provided. The three species in the complex of focus, Graphoderus elatus, Graphoderus zonatus and Graphoderus perplexus are found to have allopatric distributions; Graphoderus perplexus in the Nearctic region, Graphoderus zonatus in the west Palearctic region and eastwards to the Yenisei-Angara river and Graphoderus elatus east of the Yenisei-Angara river. All previous records of either Graphoderus zonatus or Graphoderus perplexus in the east Palearctic, east of the Yenisei-Angara river turned out to be misidentified Graphoderus elatus. This conclusion also brings with it that dimorphic females, thought only to be present in the single subspecies Graphoderus zonatus verrucifer (CR Sahlberg, 1824), proved to be present also in a second species, Graphoderus elatus. The dimorphic female forms is either with dorsally smooth elytra and pronotum or conspicuously granulated elytra and wrinkly pronotum. As has been shown in Graphoderus zonatus verrucifer there is a correlation between the occurrence of granulate female forms in a population and an increase in the number of adhesive discs on pro- and mesotarsus in males within Graphoderus elatus.