I'm wary of calling cyanobacteria with their specialized nitrogen-fixer cells or the various colonial sporangia-forming bacteria 'multicellular'. They do some hellacious cell specializing within colonies, and there are other bacteria that form chains between reducing and oxidizing environments with bacteria in the middle passing electrons back and forth so as to allow the whole colony to metabolize things one bacterium couldn't, but it's arguably a little different than what we think of when we think of a mushroom or an animal.

Eukaryotes have however evolved unambiguous multicellularity on many occasions.