Hiv, som orsakar aids, dök upp hos människor på 1900 - talet, men forskare har länge känt till att liknande virus hos apor och apor har funnits mycket längre.
En genetisk studie visar att HIV-liknande virus uppstod hos afrikanska apor och apor för 5 till 12 miljoner år sedan.
Forskningen kan en dag leda till en bättre förståelse av hiv och aids.
Hiv drabbar 34 miljoner människor över hela världen.
Sjukdomen uppstod under 1900-talet efter att ett HIV-liknande virus hoppade från schimpanser till människor.
Forskare har länge känt till att liknande virus, som kallas lentivirus, är utbredda hos afrikanska primater.
Tidigare genetisk forskning har antytt att dessa "kousiner" av hiv uppstod för tiotusentals år sedan, men vissa experter har misstänkt att detta är en underskattning.
Forskare vid University of Washington i Seattle, USA, och Fred Hutchinson Cancer Research Center, också i Seattle, tittade på genetiska signaturer av HIV-liknande virus i ett antal primater, inklusive schimpanser, gorillor, orang utans och macaques.
Förändringar i gener som har utvecklats i apors och apors immunsystem i Afrika tyder på att virusen uppstod för mellan 5 och 16 miljoner år sedan.
Forskningen, publicerad i tidskriften PLOS Pathogens, ger ledtrådar till hur våra närmaste släktingars immunsystem utvecklades för att bekämpa infektioner.
Dr Michael Emerman vid Fred Hutchinson Cancer Research Center sade: "Vår studie visar att även om primate lentivirus kan ha moderna konsekvenser för människors hälsa, de har uråldriga ursprung i våra icke-mänskliga primat släktingar."
I en kommentar till studien sade dr Sam Wilson vid MRC - University of Glasgow Centre for Virus Research i Glasgow: " Denna typ av forskning hjälper oss att förstå hur viruset fungerar.
"Förhoppningen är att det en dag ska leda till terapi."
Hiv:s ursprung kan spåras tillbaka miljoner snarare än tiotusentals år, menar forskningen.