Roughly 3 million people worldwide were receiving antiretroviral therapy (ART) at the end of 2007, but an estimated 6.7 million were still in need of treatment and a further 2.7 million became infected with HIV in 2007. Prevention efforts might reduce HIV incidence but are unlikely to eliminate this disease. We investigated a theoretical strategy of universal voluntary HIV testing and immediate treatment with ART, and examined the conditions under which the HIV epidemic could be driven towards elimination. We used mathematical models to explore the effect on the case reproduction number (stochastic model) and long-term dynamics of the HIV epidemic (deterministic transmission model) of testing all people in our test-case community (aged 15 years and older) for HIV every year and starting people on ART immediately after they are diagnosed HIV positive. We used data from South Africa as the test case for a generalised epidemic, and assumed that all HIV transmission was heterosexual. The studied strategy could greatly accelerate the transition from the present endemic phase, in which most adults living with HIV are not receiving ART, to an elimination phase, in which most are on ART, within 5 years. It could reduce HIV incidence and mortality to less than one case per 1000 people per year by 2016, or within 10 years of full implementation of the strategy, and reduce the prevalence of HIV to less than 1% within 50 years. We estimate that in 2032, the yearly cost of the present strategy and the theoretical strategy would both be US$1.7 billion; however, after this time, the cost of the present strategy would continue to increase whereas that of the theoretical strategy would decrease. Universal voluntary HIV testing and immediate ART, combined with present prevention approaches, could have a major effect on severe generalised HIV/AIDS epidemics. This approach merits further mathematical modelling, research, and broad consultation.