Brain damage is associated with linguistic deficits and might alter co-speech gesture production. Gesture production after focal brain injury has been mainly investigated with respect to intrasentential rather than discourse-level linguistic processing. In this study, we examined 1) spontaneous gesture production patterns of people with left hemisphere damage (LHD) or right hemisphere damage (RHD) in a narrative setting, 2) the neural structures associated with deviations in spontaneous gesture production in these groups, and 3) the relationship between spontaneous gesture production and discourse level linguistic processes (narrative complexity and evaluation competence). Individuals with LHD or RHD (17 people in each group) and neurotypical controls (n = 13) narrated a story from a picture book. Results showed that increase in gesture production for LHD individuals was associated with less complex narratives and lesions of individuals who produced more gestures than neurotypical individuals overlapped in frontal-temporal structures and basal ganglia. Co-speech gesture production of RHD individuals positively correlated with their evaluation competence in narrative. Lesions of RHD individuals who produced more gestures overlapped in the superior temporal gyrus and the inferior parietal lobule. Overall, LHD individuals produced more gestures than neurotypical individuals. The groups did not differ in their use of different gesture forms except that LHD individuals produced more deictic gestures per utterance than RHD individuals and controls. Our findings are consistent with the hypothesis that co-speech gesture production interacts with macro-linguistic levels of discourse and this interaction is affected by the hemispheric lateralization of discourse abilities.