Habit memory is thought to involve slowly acquired associations between stimuli and responses and to depend on the basal ganglia. Habit memory has been well studied in experimental animals but is poorly understood in humans because of their strong tendency to acquire information as conscious (declarative) knowledge. Here we show that humans have a robust capacity for gradual trial-and-error learning that operates outside awareness for what is learned and independently of the medial temporal lobe. We tested two patients with large medial temporal lobe lesions and no capacity for declarative memory. Both patients gradually acquired a standard eight-pair object discrimination task over many weeks but at the start of each session could not describe the task, the instructions or the objects. The acquired knowledge was rigidly organized, and performance collapsed when the task format was altered.