This study determines an optimal strategy for scaling up ART in Vietnam by examining three initiation thresholds [350 cells/mm3, 500 cells/mm3, and treat all people living with HIV (PLHIV) regardless of CD4 cell counts] and treatment commencement rates among treatment-eligible PLHIV ranging from 5% to 100% within 12 months of diagnosis. Incremental cost-effectiveness ratios (ICERs) were calculated using a Markov model, based on data from a cohort of 3449 patients who initiated ART between January 1, 2005 and December 31, 2009 in 13 outpatient clinics across six provinces in Vietnam. Our analyses indicated that raising treatment eligibility criteria, in line with WHO guidelines (CD4 ≤500 cells/mm3) or removing CD4-based criteria would both be cost-effective in Vietnam. However, the cost-effective strategy from an economic viewpoint is first to increase coverage substantially among those with lowest CD4 levels, and only when coverage increases towards saturation should initiation criteria be lifted. Universal coverage under current guidelines would cost an additional $85 million and $96 million per year if the treatment threshold was 500 cells/mm3. These scenarios would avert 15,000 and 22,000 HIV-related deaths in 2010-2019, with ICERs of $500-$660 per QALY gained. It is imperative to increase treatment coverage for newly diagnosed PLHIV in Vietnam according to the current guidelines prior to increasing the CD4 threshold for ART initiation.