OnabotulinumtoxinA (BonT-A) reduces migraine frequency in a considerable portion of patients with migraine. So far, predictive characteristics of response are lacking. Here, we applied machine learning (ML) algorithms to identify clinical characteristics able to predict treatment response. We collected demographic and clinical data of patients with chronic migraine (CM) or high-frequency episodic migraine (HFEM) treated with BoNT-A at our clinic in the last 5 years. Patients received BoNT-A according to the PREEMPT (Phase III Research Evaluating Migraine Prophylaxis Therapy) paradigm and were classified according to the monthly migraine days reduction in the 12 weeks after the fourth BoNT-A cycle, as compared to baseline. Data were used as input features to run ML algorithms. Of the 212 patients enrolled, 35 qualified as excellent responders to BoNT-A administration and 38 as nonresponders. None of the anamnestic characteristics were able to discriminate responders from nonresponders in the CM group. Nevertheless, a pattern of four features (age at onset of migraine, opioid use, anxiety subscore at the hospital anxiety and depression scale (HADS-a) and Migraine Disability Assessment (MIDAS) score correctly predicted response in HFEM. Our findings suggest that routine anamnestic features acquired in real-life settings cannot accurately predict BoNT-A response in migraine and call for a more complex modality of patient profiling.