Division of labor is a fundamental feature of social groups from insects to humans, but little is known about its proximate origins or functional consequences during early social evolution. Theory suggests that division of labor can emerge as a self-organizing property of group living. We examined patterns of task performance and work output during nest construction by solitary and paired individuals of the normally solitary halictine bee Lasioglossum (Ctenonomia) NDA-1. Pairs dug further and guarded the nest entrance more frequently than solitary bees. Within pairs, a division of labor repeatedly arose in which one individual specialized on excavation while her nestmate primarily guarded. Behavioral differentiation was consistent with a model based on interindividual variation in the propensity to perform specific tasks. Our findings support the hypothesis that division of labor can emerge spontaneously in incipient groups and provide insight into how selection may act on collective behavior during the transition from solitary to communal nesting in halictine bees.