Bats, like all mammals, rely on the identification of regulations and deviations in their acoustic environment. This phenomenon, called deviance detection, has been studied intensively in the past and keeps gaining attention in the field of electrophysiology. Over time, an impressive complexity of deviance detection could be shown, in both animal and human studies. However, complex forms of auditory deviance detection were so far only demonstrated for high-level brain structures. Here, we used a naturalistic acoustic stimulation protocol to demonstrate that complex deviance detection already happens in the lowest stations of the auditory pathway, the brainstem. These potentially feedback mediated effects could contribute significantly to the saving of resources very early in the processing of acoustic sounds.