We study the evolution of the halo-halo correlation function and bias in four cosmological models ( ΛCDM , OCDM , \tau CDM , and SCDM ) using very high-resolution N -body simulations with dynamical range of \sim 10 , 000 - 32 , 000 ( force resolution of \approx 2 - 4 \mbox { $h ^ { -1 } $kpc } and particle mass of \approx 10 ^ { 9 } h ^ { -1 } { M _ { \odot } } ) . The high force and mass resolution allows dark matter ( DM ) halos to survive in the tidal fields of high-density regions and thus prevents the ambiguities related with the “ overmerging problem. ” This allows us to estimate for the first time the evolution of the correlation function and bias at small ( down to \sim 100 \mbox { $h ^ { -1 } $kpc } ) scales . We find that at all epochs the 2-point correlation function of galaxy-size halos \xi _ { hh } is well approximated by a power-law with slope \approx 1.6 - 1.8 . The difference between the shape of \xi _ { hh } and the shape of the correlation function of matter results in the scale-dependent bias at scales \lesssim 7 \mbox { $h ^ { -1 } $Mpc } , which we find to be a generic prediction of the hierarchical models , independent of the epoch and of the model details . The bias evolves rapidly from a high value of \sim 2 - 5 at z \sim 3 - 7 to the anti-bias of b \sim 0.5 - 1 at small \lesssim 5 \mbox { $h ^ { -1 } $Mpc } scales at z = 0 . Another generic prediction is that the comoving amplitude of the correlation function for halos above a certain mass evolves non-monotonically : it decreases from an initially high value at z \sim 3 - 7 , and very slowly increases at z \lesssim 1 . We find that our results agree well with existing clustering data at different redshifts , indicating the general success of the hierarchical models of structure formation in which galaxies form inside the host DM halos . Particularly , we find an excellent agreement in both slope and the amplitude between \mbox { $ \xi _ { hh } $ } ( z = 0 ) in our ΛCDM _ { 60 } simulation and the galaxy correlation function measured using the APM galaxy survey . At high redshifts , the observed clustering of the Lyman-break galaxies is also well reproduced by the models . We find good agreement at z \gtrsim 2 between our results and predictions of the analytical models of bias evolution . This indicates that we have a solid understanding of the nature of the bias and of the processes that drive its evolution at these epochs . We argue , however , that at lower redshifts the evolution of the bias is driven by dynamical processes inside the nonlinear high-density regions such as galaxy clusters and groups . These processes do not depend on cosmology and tend to erase the differences in clustering properties of halos that exist between cosmological models at high z .