Consolidation of nondeclarative memory is widely believed to benefit from sleep. However, evidence is mainly limited to tasks involving rote learning of the same stimulus or behavior, and recent findings have questioned the extent of sleep-dependent consolidation. We demonstrate consolidation during sleep for a multimodal sensorimotor skill that was trained and tested in different visual-spatial virtual environments. Participants performed a task requiring the production of novel motor responses in coordination with continuously changing audio-visual stimuli. Performance improved with training, decreased following waking retention, but recovered and stabilized following sleep. These results extend the domain of sleep-dependent consolidation to more complex, adaptive behaviors.