Pirmie jebkāda veida daudzšūnu kompleksie dzīvnieki fosilajos ierakstos parādās apmēram pirms 600 līdz 590 miljoniem gadu, īpaši Tvitijas veidojumā Kanādas Makenzijas kalnos. Tie ir vienkārši kausveida dzīvnieki, kas fosilijā parādās kā vienkārši diska un gredzena nospiedumi. Tiek uzskatīts, ka tie atbilst vienkāršiem cnidarians (medūzu radiniekiem) vai sūkļiem. Tā kā šīs fosilijas ir tik vienkāršas, tās sniedz maz informācijas par dzīvniekiem, kas tos radījuši. Tomēr tos joprojām uzskata par “sarežģītiem” to ļoti lielo izmēru (apmēram collu diametrā) dēļ, salīdzinot ar vienkāršākām mikroskopiskām vienšūnu fosilijām, kas radušās pirms tām un blakus tām.
Nākamie vecākie kompleksie dzīvnieki, kas saglabājušies kā fosilijas, parādās Doushantuo veidojumā Ķīnas dienvidos un centrālajā daļā. Tiek saglabāts plašs fosilo embriju klāsts, kā arī agrākais zināmais divpusējais dzīvnieks, 0.1 mm Vernanimacula (apmēram 590–600 mya), “mazais pavasara dzīvnieks”, niecīgs lodveida dzīvnieks ar, šķiet, pārakmeņojušos. zarnas, kā arī virsmas bedrītes, kas var būt sensorās struktūras. Nelieli sarežģītu dzīvnieku, piemēram, cnidarians, fosilie embriji ir saglabāti nepārspējami detalizēti Doushantuo veidojumā, sniedzot paleontologiem svarīgu ieskatu par agrākajiem zināmajiem embrijiem.
Vēl viena agrīna fosilija sarežģītu dzīvnieku vidū ir mīklainā Cloudina, segmentēta fosilija, kas sastāv no kalcīta konusi, kas slāņoti viens uz otra. Mērot ar milimetru soli, šīs fosilijas ir vienas no pirmajām zināmajām čaulām fosiliju ierakstā. Tiem ir redzams pumpuru veidošanās, kas liek domāt, ka tie vairojās aseksuāli, kā arī plēsonīga garlaicība, kas liecina, ka plēsēji bija pat zināmās daudzšūnu dzīves rītausmā. Tāpat kā daudzas no senākajām fosilijām, trūkst neskaidrības par to, kas īsti bija Cloudina — pašreizējie viedokļi dalās starp domu, ka paraugs ir cilmes grupas annelids, un ka jebkura klasifikācija, pat patversmes līmenī, nav saprātīga. Tie var būt arheociāti, seni sūkļi, kas veidoja rifus simtiem miljonu gadu pirms koraļļu evolūcijas.
Pirmās patiesi “sarežģītās dzīvnieku” (lielākas par 1 mm, nevis cnidāriem vai koraļļiem) fosilijas ir aptuveni 575 miljonus gadu vecas, un tās ir atrodamas Mistaken Point kompleksā Ņūfaundlendā, Kanādā. Absolūti vecākais ir Charnia wardi, plaukstas formas organisms ar mainīgām izciļņiem pa kreisi un pa labi. Tā kā šīs grēdas nav pilnībā simetriskas ap centrālo asi, Charnia nav īsts divpusējs organisms, un to var raksturot tikai kā daļēji divpusēju. Sākotnēji tika aprakstīts kā jūras pildspalvu agrīnais radinieks, taču tagad zinātniekiem vienkārši nav ne jausmas, kā klasificēt Charnia.