In this paper we report on the application of a robust approach based on a reweighted least squares method for the vertex reconstruction of the CERES/NA45 experiment at the CERN SPS for the case of 160 GeV/u Pb+Au collisions and compare its performance with the presently used algorithm based on the minimization of summed Gaussian weights. In the CERES/NA45 experiment a doublet of cylindrical silicon drift detectors (SDD) is used for vertex reconstruction and tracking. The vertex reconstruction algorithm has to cope with a background-contaminated environment. Furthermore, in the case of ultrarelativistic heavy-ion collisions where high event multiplicities occur ( dn ch dη ⋍ 500 ), the probability of confusing hits from close or intersecting tracks is high. The algorithm needs to provide the precise vertex location even at high occupancies, at a reasonable speed. Our findings are that the robust iterative procedure presented here is about an order of magnitude faster than approaches using standard minimization packages, at a comparable or slightly better accuracy.