Division of labor, whereby different group members perform different functions, is a fundamental attribute of sociality. It appears across social systems, from simple cooperative groups to complex eusocial colonies. A core challenge in sociobiology is to explain how patterns of collective organization are generated. Theoretical models propose that division of labor self-organizes, or emerges, from interactions among group members and the environment; division of labor is also predicted to scale positively with group size. I empirically investigated the emergence and scaling of division of labor in evolutionarily incipient groups of sweat bees and in eusocial colonies of harvester ants. To test whether division of labor is an emergent property of group living during early social evolution, I created de novo communal groups of the normally solitary sweat bee Lasioglossum (Ctenonomia) NDA-1. A division of labor repeatedly arose between nest excavation and guarding tasks; results were consistent with hypothesized effects of spatial organization and intrinsic behavioral variability. Moreover, an experimental increase in group size spontaneously promoted higher task specialization and division of labor. Next, I examined the influence of colony size on division of labor in larger, more integrated colonies of the harvester ant Pogonomyrmex californicus. Division of labor scaled positively with colony size in two contexts: during early colony ontogeny, as colonies grew from tens to hundreds of workers, and among same-aged colonies that varied naturally in size. However, manipulation of colony size did not elicit a short-term response, suggesting that the scaling of division of labor in P. californicus colonies is a product of functional integration and underlying developmental processes, rather than a purely emergent epiphenomenon. This research provides novel insights into the organization of work in insect societies, and raises broader questions about the role of size in sociobiology.