The evolution of group living remains an outstanding question in evolutionary ecology. Among the most striking forms of group living are the enormous assemblages of breeders that occur in many colonial marine birds and mammals, with some colonies containing more than a million individuals breeding in close contact. Coloniality is an evolutionary puzzle because individuals pay fitness costs to breed in high densities. Despite numerous potential benefits proposed to overcome these costs, we still lack a general framework to explain coloniality. Several new hypotheses involving breeding habitat and mate selection create promising approaches for studying this enigma.