Flexible rule learning, a behavior with obvious adaptive value, is known to depend on an intact prefrontal cortex (PFC). One simple, yet powerful, form of such learning consists of forming arbitrary stimulus-response (S-R) associations. A variety of evidence from monkey and human studies suggests that the PFC plays an important role in both forming new S-R associations and in using learned rules to select the contextually appropriate response to a particular stimulus cue. Although monkey lesion studies more strongly implicate the ventrolateral PFC (vlPFC) in S-R learning, clinical data and neurophysiology studies have implicated both the vlPFC and the dorsolateral region (dlPFC) in associative rule learning. Previous human imaging studies of S-R learning tasks, however, have not demonstrated involvement of the dlPFC. This may be because of the design of previous imaging studies, which used few stimuli and used explicitly stated one-to-one S-R mapping rules that were usually practiced before scanning. Humans learn these rules very quickly, limiting the ability of imaging techniques to capture activity related to rule acquisition. To address these issues, we performed functional magnetic resonance imaging while subjects learned by trial and error to associate sets of abstract visual stimuli with arbitrary manual responses. Successful learning of this task required discernment of a categorical type of S-R rule in a block design expected to yield sustained rule representation. Our results show that distinct components of the dorsolateral, ventrolateral, and anterior PFC, lateral premotor cortex, supplementary motor area, and the striatum are involved in learning versus executing categorical S-R rules.