Associating stimuli with positive or negative reinforcement is essential for survival, but a complete wiring diagram of a higher-order circuit supporting associative memory has not been previously available. Here we reconstruct one such circuit at synaptic resolution, the Drosophila larval mushroom body. We find that most Kenyon cells integrate random combinations of inputs but that a subset receives stereotyped inputs from single projection neurons. This organization maximizes performance of a model output neuron on a stimulus discrimination task. We also report a novel canonical circuit in each mushroom body compartment with previously unidentified connections: reciprocal Kenyon cell to modulatory neuron connections, modulatory neuron to output neuron connections, and a surprisingly high number of recurrent connections between Kenyon cells. Stereotyped connections found between output neurons could enhance the selection of learned behaviours. The complete circuit map of the mushroom body should guide future functional studies of this learning and memory centre. The complete, synapse-resolution connectome of the Drosophila larval mushroom body. In order to guide action based on past experience, animals have evolved high-order parallel-fibre systems, such as the cerebellum in mammals and the mushroom body in the brains of certain insects. These circuits are specialized in forming large numbers of associative memories, but their full understanding has been impaired by incomplete neuro-anatomical data. Albert Cardona and colleagues provide, for the first time, a full wiring diagram at synapse resolution of such an associative system: the Drosophila larval mushroom body. The work reveals multiple novel and surprising neuronal circuits, such as both random and stereotyped inputs from projection neurons to Kenyon cells. These findings will instruct future experiments and modelling in neuroscience, psychology and robotics.