Learning of a procedural motor-skill task is known to progress through a series of unique memory stages. Performance initially improves during training, and continues to improve, without further rehearsal, across subsequent periods of sleep. Here, we investigate how this delayed sleep-dependent learning is affected when the task characteristics are varied across several degrees of difficulty, and whether this improvement differentially enhances individual transitions of the motor-sequence pattern being learned. We report that subjects show similar overnight improvements in speed whether learning a five-element unimanual sequence (17.7% improvement), a nine-element unimanual sequence (20.2%), or a five-element bimanual sequence (17.5%), but show markedly increased overnight improvement (28.9%) with a nine-element bimanual sequence. In addition, individual transitions within the motor-sequence pattern that appeared most difficult at the end of training showed a significant 17.8% increase in speed overnight, whereas those transitions that were performed most rapidly at the end of training showed only a non-significant 1.4% improvement. Together, these findings suggest that the sleep-dependent learning process selectively provides maximum benefit to motor-skill procedures that proved to be most difficult prior to sleep. (Contains 1 table and 4 figures.)