Complex bimanual motor learning causes specific changes in activation across brain regions. However, there is little information on how motor learning changes the functional connectivity between these regions, and whether this is influenced by different sensory feedback modalities. We applied graph-theoretical network analysis (GTNA) to examine functional networks based on motor-task-related fMRI activations. Two groups learned a complex 90° out-of-phase bimanual coordination pattern, receiving either visual or auditory feedback. 3T fMRI scanning occurred before (day 0) and after (day 5) training. In both groups, improved motor performance coincided with increased functional network connectivity (increased clustering coefficients, higher number of network connections and increased connection strength, and shorter communication distances). Day×feedback interactions were absent but, when examining network metrics across all examined brain regions, the visual group had a marginally better connectivity, higher connection strength, and more direct communication pathways. Removal of feedback had no acute effect on the functional connectivity of the trained networks. Hub analyses showed an importance of specific brain regions not apparent in the standard fMRI analyses. These findings indicate that GTNA can make unique contributions to the examination of functional brain connectivity in motor learning.