Information processing by the nervous system depends on neurotransmitter release from synaptic vesicles (SVs) at the presynaptic active zone. Molecular components of the cytomatrix at the active zone (CAZ) regulate the final stages of the SV cycle preceding exocytosis and thereby shape the efficacy and plasticity of synaptic transmission. Part of this regulation is reflected by a physical association of SVs with filamentous CAZ structures via largely unknown protein interactions. The very C-terminal region of Bruchpilot (Brp), a key component of the Drosophila melanogaster CAZ, participates in SV tethering. Here, we identify the conserved SNARE regulator Complexin (Cpx) in an in vivo screen for molecules that link the Brp C terminus to SVs. Brp and Cpx interact genetically and functionally. Both proteins promote SV recruitment to the Drosophila CAZ and counteract short-term synaptic depression. Analyzing SV tethering to active zone ribbons of cpx3 knockout mice supports an evolutionarily conserved role of Cpx upstream of SNARE complex assembly.