Neurexins and neuroligins provide trans-synaptic connectivity by the Ca2+-dependent interaction of their alternatively spliced extracellular domains. Neuroligins specify synapses in an activity-dependent manner, presumably by binding to neurexins. Here, we present the crystal structures of neuroligin-1 in isolation and in complex with neurexin-1 beta. Neuroligin-1 forms a constitutive dimer, and two neurexin-1 beta monomers bind to two identical surfaces on the opposite faces of the neuroligin-1 dimer to form a heterotetramer. The neuroligin-1/neurexin-1 beta complex exhibits a nanomolar affinity and includes a large binding interface that contains bound Ca2+. Alternatively spliced sites in neurexin-1 beta and in neuroligin-1 are positioned nearby the binding interface, explaining how they regulate the interaction. Structure-based mutations of neuroligin-1 at the interface disrupt binding to neurexin-1 beta, but not the folding of neuroligin-1 and confirm the validity of the binding interface of the neuroligin-1/neurexin-1 beta complex. Our results provide molecular insights for understanding the role of cell-adhesion proteins in synapse function.