The level of procedural skills improves in normal individuals when the acquisition is followed by a period of sleep rather than wake. If sleep plays an important role in the consolidation process the advantage it provides should be reduced or delayed when its organization is altered, as in patients with chronic sleep disorders. To test this prediction in patients with narcolepsy-cataplexy (NC), who usually have a more fragmented organization of sleep than normals, we compared the initial, intermediate and delayed level of consolidation of visual skills. Twenty-two drug-naive NC patients and 22 individually-matched controls underwent training at a texture discrimination task (TDT) and were re-tested on the next morning (after a night spent in laboratory with polysomnography) and after another six nights (spent at home). TDT performance was worse in patients than controls at training and at both retrieval sessions and the time course of consolidation was different in NC patients (who improved mainly from next-day to 7th-day retrieval session) compared with controls. Moreover, the less-improving patients at next-day retrieval had a wider disorganization of sleep, probably because of an episode of rapid eye movement (REM) sleep at sleep onset REM, on post-training night more frequently than more-improving patients. These findings suggest that the time course of the consolidation process of procedural skills may be widely influenced by the characteristics of sleep organization (varying night-by-night much more in NC patients than controls) during post-training night.