Eusociality represents a major transition in evolution and is typified by cooperative brood care and reproductive division of labor between generations. In bees, this division of labor allows queens and workers to phenotypically specialize. Worker traits associated with helping are thought to be crucial to the fitness of a eusocial lineage, and recent studies of honey bees (genus Apis) have found that adaptively evolving genes often have worker-biased expression patterns. It is unclear however if worker-biased genes are disproportionately acted on by strong positive selection in all eusocial insects. We undertook a comparative population genomics study of bumble bees (Bombus) and honey bees to quantify natural selection on queen- and worker-biased genes across two levels of social complexity. Despite sharing a common eusocial ancestor, genes, and gene groups with the highest levels of positive selection were often unique within each genus, indicating that life history and the environment, but not sociality per se, drives patterns of adaptive molecular evolution. We uncovered differences in the contribution of queen- and worker-biased genes to adaptive evolution in bumble bees versus honey bees. Unlike honey bees, where worker-biased genes are enriched for signs of adaptive evolution, genes experiencing positive selection in bumble bees were predominately expressed by reproductive foundresses during the initial solitary-founding stage of colonies. Our study suggests that solitary founding is a major selective pressure and that the loss of queen totipotency may cause a change in the architecture of selective pressures upon the social insect genome.