In this paper we use the ``Millennium Simulation to re-examine the mass assembly history of dark matter halos and the age dependence of halo clustering. We use eight different definitions of halo formation times to characterize the different aspects of the assembly history of a dark matter halo. We find that these formation times have different dependence on halo mass. While some formation times characterize well the hierarchical nature of halo formation, in the sense that more massive halos have later formation, the trend is reversed for other definitions of the formation time. In particular, the formation times that are likely to be related to the formation of galaxies in dark halos show strong trends of ``down-sizing, in that lower-mass halos form later. We also investigate how the correlation amplitude of dark matter halos depends on the different formation times. We find that this dependence is quite strong for some definitions of formation time but weak or absent for other definitions. In particular, the correlation amplitude of halos of a given mass is almost independent of their last major merger time. For the definitions that are expected to be more related to the formation of galaxies in dark halos, a significant assembly bias is found only for halos less massive than M_*. We discuss our results in connection to the hierarchical assembly of dark matter halos, the ``archaeological down-sizing observed in the galaxy population, and the observed color-dependence of the clustering strength of galaxy groups and clusters.