To understand the invasion history of the invasive weeds Citrullus lanatus (camel melon), Citrullus colocynthis (colocynth) and Cucumis myriocarpus (prickly paddy melon) in Australia, we studied a collection of geographically diverse samples from Africa (native range), Asia, North and South America, Europe and Australia (introduced ranges). We sequenced portions of two gene regions, the nuclear G3pdh gene and the chloroplast ycf6–psbM intergenic spacer region, to identify the diversity and relationships of alleles/haplotypes present within and among sampled populations of each species. We found that C. lanatus and C. myriocarpus populations in Australia contain negligible levels of diversity in both genes, indicative of single, genetically impoverished founder events by both species and potentially derived from single source populations in both instances. Together, historical and sequence information point to the north-western region of the Indian subcontinent as the likely source of Australian C. lanatus. Surprisingly, Australian C. myriocarpus plants share the same genetic profile as that observed in all other invasive populations of this species, but differ from that observed in native African plants. This indicates a shared origin of invasive C. myriocarpus populations and potentially a stepping-stone pathway of founder events across the globe, the origins of which are yet unidentified. In contrast, moderate levels of genetic diversity are present among Australian C. colocynthis that can be geographically sorted mainly into eastern and western regions of the continent. This suggests two separate introductions of the species into Australia, from two different source populations, most likely originating from northern Africa and/or southern Europe/Turkey. The evidence of impoverished genetic diversity in Australian populations of C. lanatus and C. myriocarpus indicates they are likely to exhibit similar responses to control measures. In contrast, development of effective chemical or bio-controls for C. colocynthis in Australia may present a greater challenge.