Prve kakršne koli večcelične kompleksne živali se pojavijo v fosilnih zapisih pred približno 600 do 590 milijoni let, natančneje v formaciji Twitya v gorovju Mackenzie v Kanadi. To so preproste živali v obliki skodelice, ki se pojavljajo v fosilni obliki kot preprosti odtisi diskov in obročev. Menijo, da ustrezajo preprostim cnidarijam (sorodnikom meduz) ali spužvam. Ker so tako preprosti, ti fosili dajejo malo informacij o živalih, ki so jih naredile. Vendar pa se še vedno štejejo za “kompleksne” zaradi svoje zelo velike velikosti (približno centimeter v premeru) v primerjavi s preprostejšimi mikroskopskimi enoceličnimi fosili pred in ob njih.
Naslednje najstarejše kompleksne živali, ohranjene kot fosili, se pojavljajo v formaciji Doushantuo na jugu osrednje Kitajske. Ohranjeni so številni fosilni zarodki, pa tudi najstarejša znana dvostranska žival, 0.1 mm Vernanimacula (približno 590 do 600 milijonov let), »majhna pomladna žival«, drobna žival v obliki krogle z nečim, kar se zdi fosilizirano. črevesje, pa tudi površinske jame, ki so lahko senzorične strukture. Drobni fosilni zarodki kompleksnih živali, kot so knidarci, so ohranjeni do neprimerljive stopnje podrobnosti v formaciji Doushantuo, kar daje paleontologom pomemben vpogled v najzgodnejše znane zarodke.
Še en zgodnji fosil med kompleksnimi živalmi je skrivnostna Cloudina, segmentirani fosil, sestavljen iz kalcitnih stožcev, naloženih drug na drugega. Ti fosili, merjeni v korakih po milimetrih, so med prvimi znanimi školjkami v fosilnem zapisu. Kažejo brstenje, kar nakazuje, da so se razmnoževale nespolno, pa tudi plenilsko dolgočasno, kar kaže, da so bili plenilci že na samem zori znanega večceličnega življenja. Tako kot pri mnogih najzgodnejših fosilih ni negotovosti glede tega, kaj točno je bil Cloudina – trenutno mnenje je razdeljeno med idejo, da je primerek anelid skupine stebel, in da je kakršna koli klasifikacija, tudi na ravni vrste, nespametna. Morda so arheociatide, starodavne spužve, ki so zgradile grebene na stotine milijonov let pred razvojem koral.
Prvi fosili zares “kompleksnih živali” (večji od 1 mm, ne čmarci ali korale) so stari približno 575 milijonov let in jih najdemo na zbirki Mistaken Point v Newfoundlandu v Kanadi. Absolutno najstarejša je Charnia wardi, lisasto oblikovan organizem z izmeničnimi grebeni levo in desno. Ker ti grebeni niso popolnoma simetrični okoli osrednje osi, Charnia ni pravi dvostranski organizem in ga lahko opišemo le kot pol-dvostranskega. Znanstveniki, ki so bili sprva opisani kot zgodnji sorodnik morskih peres, zdaj preprosto nimajo pojma, kako razvrstiti Charnia.