Our understanding of the mechanisms that establish wiring specificity of complex neural circuits is far from complete. During Drosophila olfactory circuit assembly, axons of 50 olfactory receptor neuron (ORN) classes and dendrites of 50 projection neuron (PN) classes precisely target to 50 discrete glomeruli, forming parallel information-processing pathways. Here we show that Toll-6 and Toll-7, members of the Toll receptor family best known for functions in innate immunity and embryonic patterning, cell autonomously instruct the targeting of specific classes of PN dendrites and ORN axons, respectively. The canonical ligands and downstream partners of Toll receptors in embryonic patterning and innate immunity are not required for the function of Toll-6/Toll-7 in wiring specificity, nor are their cytoplasmic domains. Interestingly, both Toll-6 and Toll-7 participate in synaptic partner matching between ORN axons and PN dendrites. Our investigations reveal that olfactory circuit assembly involves dynamic and long-range interactions between PN dendrites and ORN axons.