The HIV epidemic continues to represent one of the major problems worldwide, particularly in the Asia and Sub-Saharan regions of the world, with social and economical devastating effects. Although antiretroviral drugs have had a dramatically beneficial impact on HIV-infected individuals that have access to treatment, it has had a negligible impact on the global epidemic. Hence, the inexorable spreading of the HIV pandemic and the increasing deaths from AIDS, especially in developing countries, underscore the urgency for an effective vaccine against HIV/AIDS. However, the generation of such a vaccine has turned out to be extremely challenging. Here we provide an overview on the rationale for the use of non-structural HIV proteins, such as the Tat protein, alone or in combination with other HIV early and late structural HIV antigens, as novel, promising preventative and therapeutic HIV/AIDS vaccine strategies.