Cell adhesion represents the most direct way of coordinating synaptic connectivity in the brain. Recent evidence highlights the importance of a trans-synaptic interaction between postsynaptic neuroligins and presynaptic neurexins. These transmembrane molecules bind each other extracellularly to promote adhesion between dendrites and axons. This signals the recruitment of presynaptic and postsynaptic molecules to form a functional synapse. Remarkably, neuroligins alone can induce the formation of fully functional presynaptic terminals in contacting axons. Conversely, neurexins alone can induce postsynaptic differentiation and clustering of receptors in dendrites. Therefore, the neuroligin-neurexin interaction has the unique ability to act as a bi-directional trigger of synapse formation. Here, we review several recent studies that offer clues as to how these proteins form synapses and how they might function in the brain to establish and modify neuronal network properties and cognition.