The $^{58}$Ni$(n,gamma)^{59}$Ni cross section was measured with a combination of the activation technique and accelerator mass spectrometry (AMS). The neutron activations were performed at the Karlsruhe 3.7 MV Van de Graaff accelerator using the quasi-stellar neutron spectrum at $kT=25$ keV produced by the $^7$Li($p,n$)$^7$Be reaction. The subsequent AMS measurements were carried out at the 14 MV tandem accelerator of the Maier-Leibnitz-Laboratory in Garching using the Gas-filled Analyzing Magnet System (GAMS). Three individual samples were measured, yielding a Maxwellian-averaged cross section at $kT=30$ keV of $langlesigmarangle_{30text{keV}}$= 30.4 (23)$^{syst}$(9)$^{stat}$ mbarn. This value is slightly lower than two recently published measurements using the time-of-flight (TOF) method, but agrees within the uncertainties. Our new results also resolve the large discrepancy between older TOF measurements and our previous value.