We have measured the neutron capture cross sections of the stable magnesium isotopes Mg-24,Mg-25,Mg-26 in the energy range of interest to the s process using the neutron time-of-flight facility n_TOF at CERN. Capture events from a natural metal sample and from samples enriched in Mg-25 and Mg-26 were recorded using the total energy method based on (C6H6)-H-2 detectors. Neutron resonance parameters were extracted by a simultaneous resonance shape analysis of the present capture data and existing transmission data on a natural isotopic sample. Maxwellian-averaged capture cross sections for the three isotopes were calculated up to thermal energies of 100 keV and their impact on s-process analyses was investigated. At 30 keV the new values of the stellar cross section for Mg-24, Mg-25, and Mg-26 are 3.8 +/- 0.2 mb, 4.1 +/- 0.6 mb, and 0.14 +/- 0.01 mb, respectively.