Colletidae comprise approximately 2500 species of bees primarily distributed in the southern continents (only two colletid genera are widely distributed: Colletes and Hylaeus). Previously published studies have failed to resolve phylogenetic relationships on a worldwide basis and this has been a major barrier to the progress of research regarding systematics and evolution of colletid bees. For this study, data from four nuclear gene loci: elongation factor-1alpha (F2 copy), opsin, wingless, and 28S rRNA were analyzed for 122 species of colletid bees, representing all subfamilies and tribes currently recognized; 22 species belonging to three other bee families were used as outgroups. Bayesian, maximum likelihood, and parsimony methods were employed to investigate the phylogenetic relationships within Colletidae and resulted in highly congruent and well-resolved trees. The phylogenetic results show that Colletidae are monophyletic and that all traditionally recognized subfamilies (except Paracolletinae) are also strongly supported as monophyletic. Our phylogenetic hypothesis provides a framework within which broad questions related to the taxonomy, biogeography, morphology, evolution, and ecology of colletid bees can be addressed.