Previous studies with brain-injured patients have suggested that language abilities are necessary for complex problem-solving, even when tasks are non-verbal. In the current study, we tested this notion by analyzing behavioral and neuroimaging data from a large group of left-hemisphere stroke patients (n = 107) suffering from a range of language impairment from none to severe. Patients were tested on the Raven's Colored Progressive Matrices (RCPM), a non-verbal test of reasoning that requires participants to complete a visual pattern or sequence with one of six possible choices. For some items, the solution could be determined by visual pattern-matching, but other items required more complex, relational reasoning. As predicted, performance on the relational-reasoning items was disproportionately affected in language-impaired patients with aphasia, relative to non-aphasic, left-hemisphere patients. A voxel-based lesion symptom mapping (VLSM) procedure was used to relate patients' RCPM performance with areas of damage in the brain. Results showed that deficits on the relational reasoning problems were associated with lesions in the left middle and superior temporal gyri, regions essential for language processing, as well as in the left inferior parietal lobule. In contrast, the visual pattern-matching condition was associated with lesions in posterior portions of the left hemisphere that subserve visual processing, namely, occipital and inferotemporal cortex. These findings provide compelling support for the idea that language is critical for higher-level reasoning and problem-solving. (Contains 6 figures.)