Trapa species are floating-leaved aquatic plants with significant economic and ecological values. However, the genetic relationship within Trapa genus is unclear. Here, we evaluated the genetic relationship of 12 Trapa species/varietas and 155 individuals collected from the Yangtze River Basin (China), one of the species diversity centers of the genus. With 264 AFLP (amplified fragment length polymorphism) bands, the NJ analysis showed that all the individuals were clearly divided into groups according to their taxonomic positions and geographic origins. Both PCoA and NJ analysis further demonstrated that the two small-seed species (T. incisa and T. maximowiczii) were initially separated from the other taxa with large seeds, indicating the basal classification status of the two species. Three clustering approaches (NJ tree, STRUCTURE and PCoA) consistently exhibited a close relationship among T. bispinosa, T. quadrispinosa and T. bicornis var. cochinchinensis, which suggested that T. bicornis var. cochinchinensis, the cultivated taxon, might be of hybrid origin between T. bispinosa and T. quadrispinosa; as for T. quadrispinosa group, T. quadrispinosa var. quadrispinosa and its two variants shared the same genetic group and should be treated as one species; compared with T. japonica as a single genetic cluster, four taxa (T. natans var. pumila, T. octotuberculata, T. macropoda and T. mammillifera) were closely related, and the four taxa shared thick husks and exaggerated or deformed tubercles on seeds. This study is of great implication to provide molecular proof for phylogeny within Trapa genus, which will facilitate the utilization of natural germplasm of Trapa.