To estimate the epidemic history of HIV-1 CRF01_AE in Vietnam and adjacent Guangxi, China, we determined near full-length nucleotide sequences of CRF01_AE from a total of 33 specimens collected in 1997-1998 from different geographic regions and risk populations in Vietnam. Phylogenetic and Bayesian molecular clock analyses were performed to estimate the date of origin of CRF01_AE lineages. Our study reconstructs the timescale of CRF01_AE expansion in Vietnam and neighboring regions and suggests that the series of CRF01_AE epidemics in Vietnam arose by the sequential introduction of founder strains into new locations and risk groups. CRF01_AE appears to have been present among heterosexuals in South-Vietnam for more than a decade prior to its epidemic spread in the early 1990s. In the late 1980s, the virus spread to IDUs in Southern Vietnam and subsequently in the mid-1990s to IDUs further north. Our results indicate the northward dissemination of CRF01_AE during this time.