The Cucurbitaceae genus Austrobryonia, with four species endemic to Australia, is described, illustrated, and placed in a phylogenetic context based on molecular and morphological data. In the Flora of Australia (Telford 1982), all four species were provisionally included in Mukia, but not formally described. Austrobryonia argillicola, A. centralis, A. micrantha, and A. pilbarensis are adapted to arid central regions of Australia. All species are known from several (7–27) localities, and their distributional ranges are allopatric. A phylogenetic analysis of plastid and nuclear DNA sequences that includes all four species in a family-wide context revealed that Austrobryonia is the closest living relative to a Eurasian and Mediterranean clade consisting of Bryonia L. and Ecballium L. An rbcL molecular clock, calibrated with Cucurbitaceae fossils, dates this rare biogeographic disjunction to minimally 42 my ago (with an error of ca. ± 25%), while the crown group of Austrobryonia may be about 8 my old.