The etiological spectrum of bloodstream infections is variable between industrialized and developing countries and even within a defined location over time. We investigated trends in bloodstream infections at an infectious disease hospital in Ho Chi Minh City, Vietnam, from 1994-2008. Amongst 66,111 blood cultures performed, a clinically relevant pathogen was isolated in 7645 episodes (positivity rate; 116/1000 cultures). Salmonella Typhi was the predominant pathogen until 2002; however, a considerable annual decline in the proportion of S. Typhi was observed (OR 0.6993, 95% CI [0.6885, 0.7103], p<0.0001). Conversely, there was a significant increase in the proportions of non-typhoidal Salmonella (NTS), Cryptococcus neoformans and Penicillium marneffei, concurrent with increasing HIV prevalence. These data document a substantial longitudinal shift in bloodstream infection etiology in southern Vietnam. We propose such changes are related to increasing economic prosperity and HIV prevalence, and this pattern marks a substantial change in the epidemiology of invasive salmonellosis in Southeast Asia.