We present an analysis of the evolution of galaxy clustering in the redshift interval 0<z<4.5 in the HDF-S. The HST optical data are combined with infrared ISAAC/VLT observations, and photometric redshifts are used for all the galaxies brighter than I_AB<27.5. The clustering signal is obtained in different redshift bins using two different approaches: a standard one, which uses the best redshift estimate of each object, and a second one, which takes into account the redshift probability function of each object. This second method makes it possible to improve the information in the redshift intervals where contamination from objects with insecure redshifts is important. With both methods, we find that the clustering strength up to z~3.5 in the HDF-S is consistent with the previous results in the HDF-N. While at redshift lower than z~1 the HDF galaxy population is un/anti-biased (b<1) with respect to the underlying dark matter, at high redshift the bias increases up to b~2-3, depending on the cosmological model. These results support previous claims that, at high redshift, galaxies are preferentially located in massive haloes, as predicted by the biased galaxy formation scenario. The impact of cosmic errors on our analyses has been quantified, showing that errors in the clustering measurements in the HDF surveys are indeed dominated by shot-noise in most regimes. Future observations with instruments like the ACS on HST will improve the S/N by at least a factor of two and more detailed analyses of the errors will be required. In fact, pure shot-noise will give a smaller contribution with respect to other sources of errors, such as finite volume effects or non-Poissonian discreteness effects. Comment: 17 pages Latex, with 12 PostScript figures, Accepted for publication in MNRAS