This isn't really true. Only organisms with mitochondria developed multicellularity. Mitochondria are the hard part.

doi: 10.1073/pnas.0702207104:

Multicellularity is widely viewed as a unique attribute of eukaryotes, somehow made possible by the origin of a more complex cellular architecture and, without question, with the assistance of natural selection. However, it is difficult to defend this assertion in any formal way. Complex, multicellularity has only arisen twice, once in animals and once in vascular plants. One might add fungi to the list, although the number of fungal cell types is not large, and there is some question as to whether multicellularity was ancestral to the phylogenetic group that contains animals, fungi, and slime molds. In any event, the probability that two or three origins of multicellularity simply arose by chance within eukaryotes as opposed to prokaryotes is somewhere on the order of 1/4 to 1/2, well below the general standards of statistical validity. Of course, many other eukaryotes are capable of producing a few different cell types, but the same is true for prokaryotes, some of which produce radically different cell morphologies.