The pattern of postglacial re-colonization of Europe and the present population structure are known for various plant and animal species. The reed beetle Macroplea mutica (Fabricius, 1792) has characteristics that should influence both aspects in a peculiar way and therefore complement the currently known scenarios: It is fully aquatic but cannot swim or fly. Samples from 25 European populations of M. mutica and five specimens from China were investigated using amplified fragment length polymorphism (AFLP, 251 loci). Assessment of error rates associated with this method showed that the data set contains a strong population genetic signal. As hypothesized pronounced population differentiation and signs of inbreeding were found. Italian populations are clearly differentiated from northern populations (and from each other), which underlines the role of the Alps as a major barrier. Specimens from Lake Balaton (Hungary) show some affiliation with the populations in the Baltic Sea, which are all relatively similar. Populations from the eastern part of Northern Germany are similar to the Baltic populations, while those from the western part are allied to the British populations. The hypothesis is that the recolonization of Europe was from both the Southeast and a western refugium in the area of present-day southern England or Ireland, which resulted in a suture zone in Northern Germany. The effect of passive dispersal by drift attached to host plant material (especially in the Baltic Sea) and by zoochory (migrating waterfowl) is discussed.