Accurately predicting an outcome requires that animals learn supporting and conflicting evidence from sequential experience. In mammals and invertebrates, learned fear responses can be suppressed by experiencing predictive cues without punishment, a process called memory extinction. Here, we show that extinction of aversive memories in Drosophila requires specific dopaminergic neurons, which indicate that omission of punishment is remembered as a positive experience. Functional imaging revealed co-existence of intracellular calcium traces in different places in the mushroom body output neuron network for both the original aversive memory and a new appetitive extinction memory. Light and ultrastructural anatomy are consistent with parallel competing memories being combined within mushroom body output neurons that direct avoidance. Indeed, extinction-evoked plasticity in a pair of these neurons neutralizes the potentiated odor response imposed in the network by aversive learning. Therefore, flies track the accuracy of learned expectations by accumulating and integrating memories of conflicting events.