Obligately multicellular organisms, where cells can only reproduce as part of the group, have evolved multiple times across the tree of life. Obligate multicellularity has only evolved when clonal groups form by cell division, rather than by cells aggregating, as clonality prevents internal conflict. Yet obligately multicellular organisms still vary greatly in 'multicellular complexity' (the number of cells and cell types): some comprise a few cells and cell types, while others have billions of cells and thousands of types. Here, we test whether variation in multicellular complexity is explained by two conflict-suppressing mechanisms, namely a single-cell bottleneck at the start of development, and a strict separation of germline and somatic cells. Examining the life cycles of 129 lineages of plants, animals, fungi and algae, we show using phylogenetic comparative analyses that an early segregation of the germline stem-cell lineage is key to the evolution of more cell types, driven by a strong correlation in the Metazoa. By contrast, the presence of a strict single-cell bottleneck was not related to either the number of cells or the number of cell types, but was associated with early germline segregation. Our results suggest that segregating the germline earlier in development enabled greater evolutionary innovation, although whether this is a consequence of conflict reduction or other non-conflict effects, such as developmental flexibility, is unclear.