The Ni-58(n,gamma) cross section has been measured at the neutron time of flight facility n_TOF at CERN, in the energy range from 27 meV up to 400 keV. In total, 51 resonances have been analyzed up to 122 keV. Maxwellian averaged cross sections (MACS) have been calculated for stellar temperatures of kT = 5-100 keV with uncertainties of less than 6%, showing fair agreement with recent experimental and evaluated data up to kT = 50 keV. The MACS extracted in the present work at 30 keV is 34.2 +/- 0.6(stat) +/- 1.8(sys) mb, in agreement with latest results and evaluations, but 12% lower relative to the recent KADoNIS compilation of astrophysical cross sections. When included in models of the s-process nucleosynthesis in massive stars, this change results in a 60% increase of the abundance of Ni-58, with a negligible propagation on heavier isotopes. The reason is that, using both the old or the new MACS, Ni-58 is efficiently depleted by neutron captures.