Relationships among the tribes within Apidae are unclear. Among the most challenging phylogenetic questions within the apid bees are the phylogenetic affinities of the cleptoparasitic groups. A phylogenetic study of the family Apidae was performed based on molecular (DNA sequence) data. Sampling efforts were focused at the tribal and generic levels of the family with an emphasis on the cleptoparasitic lineages. Six nuclear protein-coding genes and two nuclear ribosomal genes were sequenced for 140 taxa. The phylogeny was then used to investigate origins of cleptoparasitism and patterns of host-parasite relationships within the family. Results indicate that there have been fewer independent origins of cleptoparasitism in the Apidae than was previously hypothesized based on morphological data. Host-parasite relationships varied throughout the family. Some cleptoparasites were closely allied to their hosts while others were distantly related. This study represents the first comprehensive tribal level phylogeny of the family Apidae based on molecular data.