Temporally precise motor sequences underlie many motor skills and innate actions, yet the flexibility with which the timing of such stereotyped behaviors can be modified is not known. To probe this, we induced adaptive changes to the temporal structure of birdsong. We find that the duration of specific song segments can be modified without affecting the timing in other parts of the song. We derive formal prescriptions for how neural networks can implement such flexible motor timing. We find that randomly connected recurrent networks, a common approximation for how neocortex is wired, do not generally conform to these, though certain implementations can approximate them. We show that feedforward networks, by virtue of their one-to-one mapping between network activity and time, are better suited. Our study provides general prescriptions for how pattern generator networks can implement flexible motor timing, an important aspect of many motor skills, including birdsong and human speech.