Skill learning is instantiated by changes to functional connectivity within premotor circuits, but whether the specificity of learning depends on structured changes to inhibitory circuitry remains unclear. We used slice electrophysiology to measure connectivity changes associated with song learning in the avian analog of primary motor cortex (robust nucleus of the arcopallium, RA) in Bengalese Finches. Before song learning, fast-spiking interneurons (FSIs) densely innervated glutamatergic projection neurons (PNs) with apparently random connectivity. After learning, there was a profound reduction in the overall strength and number of inhibitory connections, but this was accompanied by a more than two-fold enrichment in reciprocal FSI-PN connections. Moreover, in singing birds, we found that pharmacological manipulations of RA's inhibitory circuitry drove large shifts in learned vocal features, such as pitch and amplitude, without grossly disrupting the song. Our results indicate that skill learning establishes nonrandom inhibitory connectivity, and implicates this patterning in encoding specific features of learned movements.