We have measured the neutron capture cross sections of the stable magnesium isotopes 24,25,26Mg 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 25Mg and 26Mg were recorded using the total energy method based on C6 2H6 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 24Mg, 25Mg, and 26Mg are 3.8±0.2 mb, 4.1±0.6 mb, and 0.14±0.01 mb, respectively.