De första flercelliga komplexa djuren av något slag förekommer i fossilregistret för cirka 600 till 590 miljoner år sedan, särskilt i Twitya-formationen i Mackenziebergen i Kanada. Det är enkla skålformade djur som uppträder i fossil form som enkla skiv- och ringavtryck. De tros motsvara enkla cnidarians (släktingar till maneter) eller svampar. Eftersom de är så enkla, ger dessa fossiler lite information om djuren som gjorde dem. Men de anses fortfarande vara ”komplexa” på grund av sin mycket stora storlek (cirka en tum i diameter) jämfört med de enklare mikroskopiska, encelliga fossilerna från före och bredvid dem.
De näst äldsta komplexa djuren bevarade som fossil förekommer i Doushantuo-formationen i södra centrala Kina. En mängd olika fossila embryon finns bevarade, liksom det tidigaste kända bilaterala djuret, 0.1 mm Vernanimacula (ca 590 till 600 mya), det ”lilla vårdjuret”, ett litet sfärformat djur med vad som verkar vara ett fossiliserat tarm, samt ytgropar som kan vara sensoriska strukturer. Små fossila embryon från komplexa djur, såsom cnidarians, bevaras till en oöverträffad detaljgrad i Doushantuo-formationen, vilket ger paleontologer viktig inblick i de tidigaste embryona som är kända.
En annan tidig fossil bland komplexa djur är den gåtfulla Cloudina, ett segmenterat fossil som består av kalcitkoner skiktade på varandra. Mätt i steg om millimeter är dessa fossiler bland de första kända skalen i fossilregistret. De visar spirande, vilket tyder på att de förökade sig asexuellt, såväl som rovdjursbortfall, vilket visar att det fanns rovdjur även i början av känt flercelligt liv. Liksom många av de tidigaste fossilerna finns det en brist på osäkerhet om exakt vad Cloudina var – nuvarande åsikter är delad mellan tanken att exemplaret är ett stamgrupps-annelid och att all klassificering, även på filumnivå, är oklok. De kan vara archaeocyathids, gamla svampar som byggde rev hundratals miljoner år innan korallernas utveckling.
De första riktigt ”komplexa djuren” (större än 1 mm, inte cnidarians eller koraller) fossilerna är cirka 575 miljoner år gamla och finns på Mistaken Point-samlingen i Newfoundland, Kanada. Den absolut äldsta är Charnia wardi, en bladformad organism med alternerande åsar till vänster och höger. Eftersom dessa åsar inte är helt symmetriska runt den centrala axeln, är Charnia inte en sann bilateral organism, och kan endast beskrivas som semi-bilateral. Ursprungligen beskrevs som en tidig släkting till havspennor, forskare har nu helt enkelt ingen aning om hur man klassificerar Charnia.