Background: Multi-nucleos(t)ide resistance (MNR) mutations including Q151M, K65R mutations, and insertion at codon 69 of HIV-1 reverse transcriptase coding region may confer resistance to all molecules of nucleos(t)ide reverse transcriptase inhibitors (NRTI). The presence of these mutations is an emerging problem compromising non-nucleoside reverse transcriptase inhibitors and protease inhibitors-based therapies. Furthermore, factors associated with selection of these mutations are still not well defined. The current study aimed to evaluate the frequency and to characterize factors associated with the occurrence of multi-nucleos(t)ide resistance mutations among HIV-1 infected patients failing recommended first-line antiretroviral regimens in Cambodia. Methodology/Principal Finding: This is a retrospective analysis of HIV-1 drug resistance genotyping of 520 HIV-1 infected patients in virological failure (viral load > 250 copies/mL) while on first-line antiretroviral therapy in Cambodia with at least one reverse transcriptase inhibitor resistance associated mutation. Among these 520 patients, a total of 66 subjects (66/520, 12.7%) presented ≥1 MNR mutation, including Q151M, K65R, and Insert69 for 59 (11.3%), 29 (5.6%), and 2 (0.4%) patients, respectively. In multivariate analysis, both Q151M (p = 0.039) and K65R (p = 0.029) mutations were independently associated with current stavudine- compared to zidovudine-use. Conclusion: Such selection of mutations by stavudine drastically limits the choice of antiretroviral molecules available for second-line therapy in resource-limited settings. This finding supports the World Health Organization’s recommendation for stavudine phase-out.