We performed a phylogenetic analysis of the species, species groups, and subgenera within the predominantly eusocial lineage of Lasioglossum (the Hemihalictus series) based on three protein coding genes: mitochondrial cytochrome oxidase I, nuclear elongation factor 1alpha and long-wavelength rhodopsin. The entire data set consisted of 3421 aligned nucleotide sites, 854 of which were parsimony informative. Analyses by equal weights parsimony, maximum likelihood, and Bayesian methods yielded good resolution among the 53 taxa/populations, with strong bootstrap support and high posterior probabilities for most nodes. There was no significant incongruence among genes, and parsimony, maximum likelihood, and Bayesian methods yielded congruent results. We mapped social behavior onto the resulting tree for 42 of the taxa/populations to infer the likely history of social evolution within Lasioglossum. Our results indicate that eusociality had a single origin within Lasioglossum. Within the predominantly eusocial clade, however, there have been multiple (six) reversals from eusociality to solitary nesting, social polymorphism, or social parasitism, suggesting that these reversals may be more common in primitively eusocial Hymenoptera than previously anticipated. Our results support the view that eusociality is hard to evolve but easily lost. This conclusion is potentially important for understanding the early evolution of the advanced eusocial insects, such as ants, termites, and corbiculate bees.