The firing activity of dorso-medial-striatal-cholinergic interneurons (dmCINs) is a neural correlate of classical conditioning. Tonically active, they pause in response to salient stimuli, mediating acquisition of predictive cues/outcome associations. Cortical and thalamic inputs are typical of the rather limited knowledge about underlying circuitry contributing to this function. Here, we dissect the midbrain GABA and glutamate-to-dmCIN pathways and evaluate how they influence conditioned behavior. We report that midbrain neurons discriminate auditory cues and encode the association of a predictive stimulus with a footshock. Furthermore, GABA and glutamate cells form selective monosynaptic contacts onto dmCINs and di-synaptic ones via the parafascicular thalamus. Pathway-specific inhibition of each sub-circuit produces differential impairments of fear-conditioned learning. Finally, Vglut2-expressing cells discriminate between CSs although Vgat-positive neurons associate the predictive cue with the outcome. Overall, these data suggest that each component of the network carries information pertinent to sub-domains of the behavioral strategy.