Hylaeus is the only globally distributed colletid bee genus, with subgeneric and species-level diversity highest in Australia. We used one mitochondrial and two nuclear genes to reconstruct a phylogeny using Bayesian analyses of this genus based on species from Australia, Asia, Africa, Europe, Hawai'i, the New World and New Zealand. Our results concord with a ca. 30. Mya Hylaeus crown age inferred by earlier studies, and we show that Hylaeus originated in Australia. Our phylogeny indicates only two dispersal events out of Australia, both shortly after the initial diversification of extant taxa. One of these dispersals was into New Zealand with only a minor subsequent radiation, but the second dispersal out of Australia resulted in a world-wide distribution. This second dispersal and radiation event, combined with very extensive early radiation of Hyleaus in Australia, poses a conundrum: what kinds of biogeographical and ecological factors could simultaneously drive global dispersal, yet strongly constrain further successful migrations out of Australia when geographical barriers appear to be weak? We argue that for hylaeine bees movement into new niches and enemy-free spaces may have favoured initial dispersal events, but that subsequent dispersals would not have entailed the original benefits of new niche space.