Lentiviruses chronically infect a broad range of mammalian species and have been transmitted from primates to humans, giving rise to multiple outbreaks of HIV infection over the past century. Although the circumstances surrounding these recent zoonoses are becoming clearer, the nature and timescale of interaction between lentiviruses and primates remains unknown. Here, we report the discovery of an endogenous lentivirus in the genome of the gray mouse lemur (Microcebus murinus), a strepsirrhine primate from Madagascar, demonstrating that lentiviruses are capable of invading the primate germ line. Phylogenetic analysis places gray mouse lemur prosimian immunodeficiency virus (pSIVgml) basal to all known primate lentiviruses and, consistent with this, its genomic organization is intermediate between the nonprimate lentiviruses and their more derived primate counterparts. Thus, pSIVgml represents the first unambiguous example of a viral transitional form, revealing the acquisition and loss of genomic features during lentiviral evolution. Furthermore, because terrestrial mammal populations in Madagascar and Africa are likely to have been isolated from one another for at least 14 million years, the presence of pSIVgml in the gray mouse lemur genome indicates that lentiviruses must have been infecting primates for at least this period of time, or have been transmitted between Malagasy and African primate populations by a vector species capable of traversing the Mozambique channel. The discovery of pSIVgml illustrates the utility of endogenous sequences for the study of contemporary retroviruses and indicates that primate lentiviruses may be considerably older and more broadly distributed than previously thought.