According to recent estimates, 39.5 million people have been infected with HIV and 2.9 million have already died. The effect of HIV infection on individuals and communities is socially and economically devastating. Although antiretroviral drugs have had a dramatically beneficial impact on HIV-infected individuals who have access to treatment, it has had a negligible impact on the global epidemic. Therefore, the need for an efficacious HIV/AIDS vaccine remains the highest priority of the world HIV/AIDS agenda. The generation of a vaccine against HIV/AIDS has turned out to be extremely challenging, as indicated by > 20 years of unsuccessful attempts. This review discusses the major challenges in the field and key experimental evidence providing a rationale for the use of non-structural HIV proteins, such as Rev, Tat and Nef, either in the native form or expressed by viral vectors such as a replicating adeno-vector. These non-structural proteins alone or in combination with modified structural HIV-1 Env proteins represent a novel strategy for both preventative and therapeutic HIV/AIDS vaccine development.