As the most extreme expression of apparent altruism in nature, eusociality has long posed a central paradox for behavioral and evolutionary ecology. Because eusociality has arisen rarely among animals, understanding the selective pressures important in early stages of its evolution remains elusive. Employing a historical approach to this problem, we used morphology and DNA sequences to reconstruct the phylogeny of 13 species of sponge-dwelling shrimps (Synalpheus) with colony organization ranging from asocial pair-bonding through eusociality. We then used phylogenetically independent contrasts to test whether sociality was associated with evidence of enhanced competitive ability, as suggested by hypotheses invoking an advantage of cooperation in crowded habitats. The molecular, morphological, and combined data each strongly supported three independent origins of monogynous, multigenerational (eusocial) colony organization within this genus. Phylogenetically independent contrasts confirmed that highly social taxa, with strong reproductive skew, have significantly higher relative abundance within the host sponge than do less social taxa, a result that was robust to uncertainty in tree topology and varying models of character change. A similar tendency for highly social species to share their sponge with fewer congener species was suggestive, but not significant. Because unoccupied habitat appears to be limiting for many sponge-dwelling shrimp species, these data are consistent with hypotheses that cooperative social groups enjoy a competitive advantage over less organized groups or individuals, where independent establishment is difficult, and that enemy pressure is of central importance in the evolution of animal sociality.