Multicellularity appeared early and repeatedly in life's history; its instantiations presumably required the confluence of environmental, ecological, and genetic factors. Comparisons of several independently evolved pairs of multicellular and unicellular relatives indicate that transitions to multicellularity are typically associated with increases in the numbers of genes involved in cell differentiation, cell-cell communication, and adhesion. Further examination of the DNA record suggests that these increases in gene complexity are the product of evolutionary innovation, tinkering, and expansion of genetic material. Arguably, the most decisive multicellular transition was the emergence of animals. Decades of developmental work have demarcated the genetic toolkit for animal multicellularity, a select set of a few hundred genes from a few dozen gene families involved in adhesion, communication, and differentiation. Examination of the DNA records of the earliest-branching animal phyla and their closest protist relatives has begun to shed light on the origins and assembly of this toolkit. Emerging data favor a model of gradual assembly, with components originating and diversifying at different time points prior to or shortly after the origin of animals.