Multicellular complexity is a central topic in biology, but the evolutionary processes underlying its origin are difficult to study and remain poorly understood. Here we use experimental evolution to investigate the tempo and mode of multicellular adaptation during a de novo evolutionary transition to multicellularity. Multicelled "snowflake" yeast evolved from a unicellular ancestor after 7 days of selection for faster settling through liquid media. Over the next 220 days, snowflake yeast evolved to settle 44% more quickly. Throughout the experiment the clusters evolved faster settling by three distinct modes. The number of cells per cluster increased from a mean of 42 cells after 7 days of selection to 114 cells after 227 days. Between days 28 and 65, larger clusters evolved via a twofold increase in the mass of individual cells. By day 227, snowflake yeast evolved to form more hydrodynamic clusters that settle more quickly for their size than ancestral strains. The timing and nature of adaptation in our experiment suggests that costs associated with large cluster size favor novel multicellular adaptations, increasing organismal complexity.