The primate lentiviruses comprise SIV strains from various host species, as well as two viruses, HIV-1 and HIV-2, that cause AIDS in humans. The origins of HIV-1 and HIV-2 have been traced to cross-species transmissions from chimpanzees and sooty mangabey monkeys respectively. Two approaches have been taken to estimate the time-scale of the evolution of these viruses. Certain groups of SIV strains appear to have evolved in a host-dependent manner, implying a time-scale of many thousands or even millions of years. In stark contrast, molecular clock calculations have previously been used to estimate a time-scale of only tens or hundreds of years. Those calculations largely ignored heterogeneity of evolutionary rates across different sites within sequences. In fact, the distribution of rates at different sites seems extremely skewed in HIV-1, and so the time-depth of the primate lentivirus evolutionary tree may have been underestimated by at least a factor of ten. However, these date estimates still seem to be far too recent to be consistent with host-dependent evolution.