The hallmark of a major evolutionary transition, whereby independently replicating units became grouped together into larger wholes, is the “decoupling” of fitness of the collective from the individual fitnesses of the units. It is widely believed that the key element making such decoupling possible is extensive cooperation between the lower-level entities. Here, it is demonstrated that cohesive multicellular behavior can arise in a purely competitive setting as a generic consequence of division of labor. A minimal theoretical model of competitive coexistence on multiple resources provides an explicit manifestation of fitness decoupling in a rigorous mathematical sense. This form of multicellular behavior is not vulnerable to “cheaters” and can be expected to be widespread in microbial ecosystems.