Understanding how sterile worker castes in social insects first evolved is one of the supreme puzzles in social evolution. Here, we show that in the bee tribe Allodapini, the earliest societies did not entail a foraging worker caste, but instead comprised females sharing a nest with supersedure of dominance. Subordinates delayed foraging until they became reproductively active, whereupon they provided food for their own brood as well as for those of previously dominant females. The earliest allodapine societies are, therefore, not consistent with an 'evo-devo' paradigm, where decoupling of foraging and reproductive tasks is proposed as a key early step in social evolution. Important features of these ancestral societies were insurance benefits for dominants, headstart benefits for subordinates and direct reproduction for both. The two lineages where morphologically distinct foraging worker castes evolved both occur in ecosystems with severe constraints on independent nesting and where brood rearing periods are very seasonally restricted. These conditions would have strongly curtailed dispersal options and increased the likelihood that dominance supersedure occurred after brood rearing opportunities were largely degraded. The origins of foraging castes, therefore, represented a shift towards assured fitness gains by subordinates, mediated by the dual constraints of social hierarchies and environmental harshness.