Proteomic studies of the composition of mammalian synapses have revealed a high degree of complexity. The postsynaptic and presynaptic terminals are molecular systems with highly organized protein networks producing emergent physiological and behavioral properties. The major classes of synapse proteins and their respective functions in intercellular communication and adaptive responses evolved in prokaryotes and eukaryotes prior to the origins of neurons in metazoa. In eukaryotes, the organization of individual proteins into multiprotein complexes comprising scaffold proteins, receptors, and signaling enzymes formed the precursor to the core adaptive machinery of the metazoan postsynaptic terminal. Multiplicative increases in the complexity of this protosynapse machinery secondary to genome duplications drove synaptic, neuronal, and behavioral novelty in vertebrates. Natural selection has constrained diversification in mammalian postsynaptic mechanisms and the repertoire of adaptive and innate behaviors. The evolution and organization of synapse proteomes underlie the origins and complexity of nervous systems and behavior.