There is a need to enhance watermelon cultivars for disease and pest resistance. U.S. Plant Introductions (PIs) of Citrullus lanatus (Thunb.) Matsum. et Nakai subsp. lanatus var. citroides (Bailey) Mansf. ex Greb. collected in southern Africa are a valuable source for enhancing disease and pest resistance in watermelon cultivars. They are also valuable as rootstocks for grafted watermelon, particularly in fields infested with root-knot nematodes or fusarium wilt. However, there is limited information about genetic diversity among these PIs. In this study, we used “high frequency oligonucleotide - targeting active gene (HFO-TAG)” markers to evaluate genetic diversity and phylogenetic relationships among 96 Citrullus PIs and cultivars. Cluster and multidimensional scaling plot analysis produced distinct groups of the C. lanatus var. citroides, C. lanatus var. lanatus and C. colocynthis PIs. Population structure analysis identified sets of alleles that are predominant in each of the Citrullus groups examined here. Several PIs that are in the transitional position showed genetic admixture, having a variety of alleles from each of the major Citrullus groups. Overall, wide genetic divergence exists among the Citrullus PIs. Several of those PIs with a wide genetic distance between them and with resistance to root-knot nematodes were identified as possible candidates for further studies to develop heterotic F1 hybrid rootstock lines for grafted watermelon.