A simple epithelium forms a barrier between the outside and the inside of an organism, and is the first organized multicellular tissue found in evolution. We examine the relationship between the evolution of epithelia and specialized cell-cell adhesion proteins comprising the classical cadherin/?-catenin/?-catenin complex (CCC). A review of the divergent functional properties of the CCC in metazoans and non-metazoans, and an updated phylogenetic coverage of the CCC using recent genomic data reveal: (1) The core CCC likely originated before the last common ancestor of unikonts and their closest bikont sister taxa. (2) Formation of the CCC may have constrained sequence evolution of the classical cadherin cytoplasmic domain and ?-catenin in metazoa. (3) The ?-catenin-binding domain in ?-catenin appears to be the favored mutation site for disrupting ?-catenin function in the CCC. (4) The ancestral function of the ?/?-catenin heterodimer appears to be an actin-binding module. In some metazoan groups, more complex functions of ?-catenin were gained by sequence divergence in the non-actin-binding (N-, M-) domains. (5) Allosteric regulation of ?-catenin may have evolved for more complex regulation of the actin cytoskeleton.