Functional specialization, or division of labour (DOL), of parts within organisms and colonies is common in most multi-cellular, colonial and social organisms, but it is far from ubiquitous. Several mechanisms have been proposed to explain the evolutionary origins of DOL; the basic feature common to all of them is that functional differences can arise easily. These mechanisms cannot explain the many groups of colonial and social animals that exhibit no DOL despite up to 500 million years of evolution. Here, I propose a new hypothesis, based on a multi-level selection theory, which predicts that a reproductive DOL is required to evolve prior to subsequent functional specialization. I test this hypothesis using a dataset consisting of the type of DOL for living and extinct colonial and social animals. The frequency distribution of DOL and the sequence of its acquisition confirm that reproductive specialization evolves prior to functional specialization. A corollary of this hypothesis is observed in colonial, social and also within multi-cellular organisms; those species without a reproductive DOL have a smaller range of internal variation, in terms of the number of polymorphs or cell types, than species with a reproductive DOL.