The post-synaptic complex, a membrane specialization for signaling and synaptic plasticity, constitutes an important component of nerve cells. Tracking the early origins of the genes that make up this complex has not been possible without genomic information from the earliest branching animals. In this study, the origin and evolution of this complex are investigated by comparative genomics of animal species and their closest uni-cellular relatives. First, by conducting extensive phylogenetic analyses on gene families that constitute the vertebrate synapse, it is shown that the genome of a sea sponge, an animal without a nervous system, possesses a post-synaptic scaffold. Second, a new algorithm is introduced to automatically generate evolutionary histories of gene families. This algorithm and other bioinformatics techniques are employed to study the evolutionary descent of synaptic protein domains. One important protein-protein interaction domain in the synapse is the PDZ domain. The results show that positive selection acting on just a few PDZ domain residues was exploited by evolution to diversify the types of possible binding interactions that had eventually enabled the evolution of membrane scaffolds such as the post-synaptic complex.