Disturbances of semantic and phonemic fluency are common after brain damage, as a manifestation of language, executive, or memory dysfunction. Lesion-symptom mapping (LSM) studies can provide fundamental insights in shared and distinct anatomical correlates of these cognitive functions and help to understand which patients suffer from these deficits. We performed a multivariate support vector regression-based lesion-symptom mapping and structural disconnection study on semantic and phonemic fluency in 1231 patients with acute ischemic stroke. With the largest-ever LSM study on verbal fluency we achieved almost complete brain lesion coverage. Lower performance on both fluency types was related to left hemispheric frontotemporal and parietal cortical regions, and subcortical regions centering on the left thalamus. Distinct correlates for phonemic fluency were the anterior divisions of middle and inferior frontal gyri. Distinct correlates for semantic fluency were the posterior regions of the middle and inferior temporal gyri, parahippocampal and fusiform gyri and triangular part of the inferior frontal gyrus. The disconnectome-based analyses additionally revealed phonemic fluency was associated with a more extensive frontoparietal white matter network, whereas semantic fluency was associated with disconnection of the fornix, mesiotemporal white matter, splenium of the corpus callosum. These results provide the most detailed outline of the anatomical correlates of phonemic and semantic fluency to date, stress the crucial role of subcortical regions and reveal a novel dissociation in the left temporal lobe.