ABSTRACT: BACKGROUND: Melon, Cucumis melo, and cucumber, C. sativus, are among the most widely cultivated crops worldwide. Cucumis, as traditionally conceived, is geographically centered in Africa, with C. sativus and C. hystrix thought to be the only Cucumis species in Asia. This taxonomy forms the basis for all ongoing Cucumis breeding and genomics efforts. We tested relationships among Cucumis and related genera based on DNA sequences from chloroplast gene, intron, and spacer regions (rbcL, matK, rpl20-rps12, trnL, and trnL-F), adding nuclear internal transcribed spacer sequences to resolve relationships within Cucumis. RESULTS: Analyses of combined chloroplast sequences (4,375 aligned nucleotides) for 123 of the 130 genera of Cucurbitaceae indicate that the genera Cucumella, Dicaelospermum, Mukia, Myrmecosicyos, and Oreosyce are embedded within Cucumis. Phylogenetic trees from nuclear sequences for these taxa are congruent, and the combined data yield a well-supported phylogeny. The nesting of the five genera in Cucumis greatly changes the natural geographic range of the genus, extending it throughout the Malesian region and into Australia. The closest relative of Cucumis is Muellerargia, with one species in Australia and Indonesia, the other in Madagascar. Cucumber and its sister species, C. hystrix, are nested among Australian, Malaysian, and Western Indian species placed in Mukia or Dicaelospermum and in one case not yet formally described. Cucumis melo is sister to this Australian/Asian clade, rather than being close to African species as previously thought. Molecular clocks indicate that the deepest divergences in Cucumis, including the split between C. melo and its Australian/Asian sister clade, go back to the mid-Eocene. CONCLUSION: Based on congruent nuclear and chloroplast phylogenies we conclude that Cucumis comprises an old Australian/Asian component that was heretofore unsuspected. Cucumis sativus evolved within this Australian/Asian clade and is phylogenetically far more distant from C. melo than implied by the current morphological classification.