Multicellularity spans a wide gamut in terms of complexity, from simple clonal clusters of cells to large-scale organisms composed of differentiated cells and tissues. While recent experiments have demonstrated that simple forms of multicellularity can readily evolve in response to different selective pressures, it is unknown if continued exposure to those same selective pressures will result in the evolution of increased multicellular complexity. We use mathematical models to consider the adaptive trajectories of unicellular organisms exposed to periodic bouts of abiotic stress, such as drought or antibiotics. Populations can improve survival in response to the stress by evolving multicellularity or cell differentiation—or both; however, these responses have associated costs when the stress is absent. We define a parameter space of fitness-relevant traits and identify where multicellularity, differentiation, or their combination is fittest. We then study the effects of adaptation by allowing populations to fix mutations that improve their fitness. We find that while the same mutation can be beneficial to populations of different complexity, e.g., strict unicellularity or life cycles with stages of differentiated multicellularity, the magnitudes of their effects can differ and alter which is fittest. As a result, we observe adaptive trajectories that gain and lose complexity. We also show that the order of mutations, historical contingency, can cause some transitions to be permanent in the absence of neutral evolution. Ultimately, we find that continued exposure to a selective driver for multicellularity can either lead to increasing complexity or a return to unicellularity.