Mining newly sequenced genomes of basal metazoan organisms reveals the evolutionary origin of modern protein families. Specific cell-cell adhesion and intracellular communication are key processes in multicellular animals, and members of the cadherin superfamily are essential players in these processes. Mammalian genomes contain over 100 genes belonging to this superfamily. By a combination of tBLASTn and profile hidden Markov model analyses, we made an exhaustive search for cadherins and compiled the cadherin repertoires in key organisms, including Branchiostoma floridae (amphioxus), the sea anemone Nematostella vectensis, and the placozoan Trichoplax adhaerens. Comparative analyses of multiple protein domains within known and novel cadherins enabled us to reconstruct the complex evolution in metazoa of this large superfamily. Five main cadherin branches are represented in the primitive metazoan Trichoplax: classical (CDH), flamingo (CELSR), dachsous (DCHS), FAT, and FAT-like. Classical cadherins, such as E-cadherin, arose from an Urmetazoan cadherin, which progressively lost N-terminal extracellular cadherin repeats, whereas its cytoplasmic domain, which binds the armadillo proteins p120ctn and β-catenin, remained quite conserved from placozoa to man. The origin of protocadherins predates the Bilateria and is likely rooted in an ancestral FAT cadherin. Several but not all protostomians lost protocadherins. The emergence of chordates coincided with a great expansion of the protocadherin repertoire. The evolution of ancient metazoan cadherins points to their unique and crucial roles in multicellular animal life.