Objectives: To investigate the structural changes of hippocampus and amygdala and their relationships with migraine frequency and prognosis. Methods: Hippocampus and amygdala volumes were measured by 3-T brain magnetic resonance imaging (MRI) in 31 controls and 122 migraine patients who were categorized into eight groups by headache frequency: group 1 (1–2 headache days/month), 2 (3–4), 3 (5–7), 4 (8–10), 5 (11–14), 6 (15–19), 7 (20–24), and 8 (25–30). Headache frequency was reassessed 2 years later and a frequency reduction ≥50% was regarded a good outcome. Results: Hippocampus and amygdala volumes fluctuated in patient groups but did not differ from the controls. In migraine patients, the bilateral hippocampus volumes peaked in group 3. The volumes and headache frequencies correlated positively in groups 2–3 on bilateral sides (L: r = 0.44, p = 0.007; R: r = 0.35, p = 0.037), and negatively in groups 3–7 on the left side (5–24 days/month; L: r = −0.31, p = 0.004) and groups 3–8 on the right side (r = −0.31, p = 0.002). The left amygdala volume also peaked in group 3, and correlated with headache frequency in groups 1–3 (r = 0.34, p = 0.020) and groups 3–6 (r = −0.30, p = 0.012). The volumetric changes of the right amygdala with headache frequency did not reach statistical significance. At 2-year follow-up, the right hippocampus volume was positively associated with a good migraine outcome after adjustment of headache frequency (OR 4.72, p = 0.024). Conclusions: Hippocampus and amygdala display a structural plasticity linked to both headache frequency and clinical outcome of migraine.