All animal locomotion is rhythmic, whether it is achieved through undulation of the whole body or the coordinated movement of articulated limbs. Neurobiologists have long studied circuits that produce rhythmic activity with non-rhythmic input, also called central pattern generators (CPGs). However, the cellular and microcircuit implementation of a walking CPG has never been described for any limbed animal. Brand new comprehensive connectomes of the fruit fly ventral nerve cord (VNC) provide an opportunity to study rhythmogenic walking circuits at a synaptic resolution. In this project, we developed a data-driven network modeling approach to identify and characterize CPGs in the Drosophila leg motor system. We took the static synaptic connectivity matrix from the VNC connectome as synaptic weights in a firing rate model to simulate each neuron's dynamic activity given different inputs and manipulations. We restricted our analysis to the front two legs and considered all motor, premotor, and descending neurons in the corresponding neuropils. In a computational screen of individual excitatory descending neurons activated with a tonic input, we found only a small subset generated rhythmic motor neuron output. Encouragingly, one of the most robustly rhythm-generating descending neuron types is the BDN2 neuron. Bilateral stimulation of BDN2 neurons was recently shown experimentally to be sufficient to drive forward walking in intact or headless flies. To identify a minimal circuit for walking, we applied tonic input to BDN2 descending neurons while iteratively pruning interneurons in a greedy algorithm. Using this approach, we identified a minimal circuit with just three VNC local interneurons that are necessary and sufficient to generate rhythmic motor neuron activity across several leg segments in response to descending BDN2 drive. We hypothesize that these interneurons form the core of a walking CPG in insects, and this candidate circuit can be genetically targeted for experimental recording and manipulation.