Genome level information coupled with phylogenetic analysis of specific genes and gene families allow for a better understanding of the structure and function of their protein products. In this study, we examine the mammalian uroplakins (UPs) Ia and Ib, members of the tetraspanin superfamily, that interact with uroplakins UPII and UPIIIa/IIIb, respectively, using a phylogenetic approach of these genes from whole genome sequences. These proteins interact to form urothelial plaques that play a central role in the permeability barrier function of the apical urothelial surface of the urinary bladder. Since these plaques are found exclusively in mammalian urothelium, it is enigmatic that UP-like genomic sequences were recently found in lower vertebrates without a typical urothelium. We have cloned full-length UP-related cDNAs from frog (Xenopus laevis), chicken (Gallus gallus), and zebrafish (Danio rerio), and combined these data with sequence information from their orthologs in all the available fully sequenced and annotated animal genomes. Phylogenetic analyses of all the available uroplakin sequences, and an understanding of their distribution in several animal taxa, suggest that: (i) the UPIa/UPIb and UPII/UPIII genes evolved by gene duplication in the common ancestor of vertebrates; (ii) uroplakins can be lost in different combinations in vertebrate lineages; and (iii) there is a strong co-evolutionary relationship between UPIa and UPIb and their partners UPII and UPIIIa/IIIb, respectively. The co-evolution of the tetraspanin UPs and their associated proteins may fine-tune the structure and function of uroplakin complexes enabling them to perform diverse species- and tissue-specific functions. The structure and function of uroplakins, which are also expressed in Xenopus kidney, oocytes and fat body, are much more versatile than hitherto appreciated.