During neurorehabilitation, the re-learning of motor sequences is crucial for patients with motor deficits, enabling them to master again complex movements. A recent study showed that patients with left hemisphere (LH) stroke exhibited preserved motor sequence learning (as assessed by the serial reaction time (SRT) task) when the timing of the stimuli was comparable in the training and later test phase. However, patients showed significantly smaller learning scores as compared to healthy controls when the temporal delay between the patient's motor response and the following stimulus was randomized in the test phase. We here investigated whether LH stroke patients were able to learn spatial motor sequences even if no predictable temporal information was provided (i.e., adopting random response-stimulus intervals, RSIs) already during the training phase. Twelve right-handed LH stroke patients and 18 right-handed healthy controls performed a SRT task with random RSIs to test incidental learning of a complex spatial motor sequence. Results indicate that, although the learning condition with random RSIs was more difficult than learning with predictable RSIs, LH stroke patients performed as well as healthy controls regarding sequence specific learning. Thus, data show for the first time that LH stroke patients are able to incidentally learn a spatial sequence even when no predictable temporal information is available.