The genetic relationships among 27 watermelon cultigens (Citrullus lanatus var. lanatus) from different countries of origin and with different horticultural characteristics and 5 related wild-type species and subspecies (Citrullus colocynthis, Citrullus lanatus var. citroides, and Citrullus rehmii) were assessed using amplified fragment length polymorphism (AFLP) and expressed sequence tag-simple sequence repeat (EST-SSR) markers. AFLPs were evaluated using 16 EcoRI-MseI primer combinations, and 862 alleles (an average of 53 alleles per primer combination) were scored. Polymorphisms were found in 806 (93.4%) alleles, whereas 56 monomorphic alleles were identified. Using 16 EST-SSR primer sets, 103 alleles were scored, and all 103 alleles were polymorphic among the 32 genotypes with an average of 6.4 polymorphic alleles per primer pair. However, the high polymorphic ratio among the AFLPs and EST-SSRs was largely due to the wild-type species, while little diversity was observed among the adapted cultivars. Genetic similarity coefficients were calculated based on the 965 polymorphic AFLP and EST-SSR alleles, and a phenetic tree was constructed. The dendrogram contained 2 major clusters. Cluster I included all adapted watermelon cultivars, and the similarity among these cultigens was very high (0.94–0.98), demonstrating cross relationships and a narrow genetic background. Cluster II was composed of 4 wild-type species. The genetic distance between the nodes that comprise these 2 clusters was approximately 0.63, indicating a high level of genetic dissimilarity between the adapted watermelon species and the other related species. The low level of marker polymorphism among the adapted cultivars implies that a severe bottleneck in genetic diversity existed in watermelon during the initial breeding practices.