Inflexible cognition and behavior are prominent features of prefrontal cortex damage and several neuropsychiatric disorders. The ability to flexibly adapt cognitive processing and behavior to dynamically changing environmental contingencies has been studied using the reversal learning paradigm in mammals, but the complexity of the brain circuits precludes a detailed analysis of the underlying neural mechanism. Here we study the neural circuitry mechanism supporting flexible behavior in a genetically tractable model organism, Drosophila melanogaster. Combining quantitative behavior analysis and genetic manipulation, we found that inhibition from a single pair of giant GABAergic neurons, the anterior paired lateral (APL) neurons, onto the mushroom bodies (MBs) selectively facilitates behavioral flexibility during visual reversal learning. This effect was mediated by ionotropic GABA(A) receptors in the MB. Moreover, flies with perturbed MB output recapitulated the poor reversal performance of flies with dysfunctional APL neurons. Importantly, we observed that flies with dysfunctional APL-MB circuit performed normally in simple forms of visual learning, including initial learning, extinction, and differential conditioning. Finally, we showed that acute disruption of the APL-MB circuit is sufficient to impair visual reversal learning. Together, these data suggest that the APL-MB circuit plays an essential role in the resolution of conflicting reinforcement contingencies and reveals an inhibitory neural mechanism underlying flexible behavior in Drosophila.