Cluster headache is characterized by recurrent, unilateral attacks of excruciating pain associated with ipsilateral cranial autonomic symptoms. Although a wide array of clinical, anatomical, physiological, and genetic data have informed multiple theories about the underlying pathophysiology, the lack of a comprehensive mechanistic understanding has inhibited, on the one hand, the development of new treatments and, on the other, the identification of features predictive of response to established ones. The first-line drug, verapamil, is found to be effective in only half of all patients, and after several weeks of dose escalation, rendering therapeutic selection both uncertain and slow. Here we use high-dimensional modelling of routinely acquired phenotypic and MRI data to quantify the predictability of verapamil responsiveness and to illuminate its neural dependants, across a cohort of 708 patients evaluated for cluster headache at the National Hospital for Neurology and Neurosurgery between 2007 and 2017. We derive a succinct latent representation of cluster headache from non-linear dimensionality reduction of structured clinical features, revealing novel phenotypic clusters. In a subset of patients, we show that individually predictive models based on gradient boosting machines can predict verapamil responsiveness from clinical (410 patients) and imaging (194 patients) features. Models combining clinical and imaging data establish the first benchmark for predicting verapamil responsiveness, with an area under the receiver operating characteristic curve of 0.689 on cross-validation (95% confidence interval: 0.651 to 0.710) and 0.621 on held-out data. In the imaged patients, voxel-based morphometry revealed a grey matter cluster in lobule VI of the cerebellum (-4, -66, -20) exhibiting enhanced grey matter concentrations in verapamil non-responders compared with responders (familywise error-corrected P = 0.008, 29 voxels). We propose a mechanism for the therapeutic effect of verapamil that draws on the neuroanatomy and neurochemistry of the identified region. Our results reveal previously unrecognized high-dimensional structure within the phenotypic landscape of cluster headache that enables prediction of treatment response with modest fidelity. An analogous approach applied to larger, globally representative datasets could facilitate data-driven redefinition of diagnostic criteria and stronger, more generalizable predictive models of treatment responsiveness.