The majority of operations carried out by the brain require learning complex signal patterns for future recognition, retrieval and reuse. Although learning is thought to depend on multiple forms of long-term synaptic plasticity, the way this latter contributes to pattern recognition is still poorly understood. Here, we have used a simple model of afferent excitatory neurons and interneurons with lateral inhibition, reproducing a network topology found in many brain areas from the cerebellum to cortical columns. When endowed with spike-timing dependent plasticity (STDP) at the excitatory input synapses and at the inhibitory interneuron–interneuron synapses, the interneurons rapidly learned complex input patterns. Interestingly, induction of plasticity required that the network be entrained into theta-frequency band oscillations, setting the internal phase-reference required to drive STDP. Inhibitory plasticity effectively distributed multiple patterns among available interneurons, thus allowing the simultaneous detection of multiple overlapping patterns. The addition of plasticity in intrinsic excitability made the system more robust allowing self-adjustment and rescaling in response to a broad range of input patterns. The combination of plasticity in lateral inhibitory connections and homeostatic mechanisms in the inhibitory interneurons optimized mutual information (MI) transfer. The storage of multiple complex patterns in plastic interneuron networks could be critical for the generation of sparse representations of information in excitatory neuron populations falling under their control.