We report new assemblages of well-preserved organic-walled microfossils from the >1.648 Ga Mallapunyah Formation (McArthur Group) and the 1.78-1.73 Ga McDermott Formation (Tawallah Group), McArthur Basin, Australia. These assemblages include entangled filamentous sheaths, pseudobranching filaments and akinete-like vesicles of probable cyanobacterial origin; smooth-walled vesicles, with diverse shapes, wall textures and size (up to few hundred microns), excystment structures or budding; and vesicles ornamented with concentric striations (Valeria), equatorial flange (Simia), organic plates (Dictyosphaera), and processes and other expansions from the vesicle wall (Tappania). Known fossil bacterial walls and sheaths do not show such wall ornamentation. Although filamentous protrusions are known in one archaeon and in PVC Bacteria, showing that prokaryotes may show complex morphologies supported by their cytoskeleton, the microfossils size strongly differ by one or two orders of magnitude from them. In contrast, the morphological complexity of fossils reported here is only known in eukaryotes and implies cytological sophistication for the synthesis of organic plates, external equatorial outgrowth, internal concentric ridges, and diverse protrusions indirectly evidencing the presence of a cytoskeleton. Collectively, these assemblages reveal an ecosystem with cyanobacterial mat fragments, diverse prokaryotic or eukaryotic cells, various stages of life cycle, and ornamented protists, known in the late Paleoproterozoic-Mesoproterozoic. This record pushes back the minimum age of eukaryotic fossils, previously reported at ~1.65 Ga in China and Australia.