“… both believe that a capacity for multicellularity evolved early in life’s history and is shared with bacteria’s ancient cousins, the archaea, which also seem unicellular.”

Link. The eukaryotic cell seems a tiny bit less impossible.