PDZ domains are protein-protein interaction modules widely used to assemble membranous signaling complexes including those found in the neuronal synapse. PDZ-containing genes encoded in metazoan genomes vastly outnumber those in prokaryotes, plants, and fungi. By comparing 40 proteomes to track the evolutionary history of the PDZ domain, we observed that the variety of associations between PDZ and other domains expands greatly along the stem leading to metazoans and choanoflagellates. We asked whether the expansion of PDZ domains was due to random or specific sequence changes. Studying the sequence signatures of 58 PDZ lineages that are common to bilaterian animals, we showed that six common amino acid residues are able to classify 96% of PDZ domains to their correct evolutionary lineage. In PDZ domain-ligand cocrystals, four of these "classifying positions" lie in direct contact with the -1 and -3 residues of the ligand. This suggests coevolution of the more flexible regions of the binding interaction as a central mechanism of specialization inherent within the PDZ domain. To identify these positions, we devised two independent algorithms--a metric termed within-clade entropy (WCE) and an average mutual information (AvgMI) score--that both reached similar results. Extending these tools to the choanoflagellate, Monosiga brevicollis, we compared its PDZ domains with their putative metazoan orthologs. Interestingly, the M. brevicollis genes lack conservation at the classifying positions suggesting dissociation between domain organization in multidomain proteins and specific changes within the PDZ domain.