More than 60 million individuals have been infected with HIV and approximately half of these individuals have died since the epidemic started. The quest for an effective vaccine to prevent HIV transmission, which is likely to be the most effective approach to halt the epidemic, has been and continues to be an insurmountable challenge. Traditional vaccine strategies that have been effective for other vaccines have proven unsuccessful or impractical for HIV because of safety concerns. Nonetheless, substantial efforts have been directed at the development and clinical testing of HIV vaccines during the past two decades. Four major HIV vaccine efficacy trials conducted by VaxGen Inc (AIDSVAX 003 and AIDSVAX 004) and the NIH-supported HIV Vaccine Trials Network (HVTN 502 and HVTN 503) failed to demonstrate efficacy; however, a recent trial conducted in Thailand (RV144 trial) demonstrated a low level of efficacy, resulting in some renewed optimism. Dissecting the causes for vaccine failure and, more importantly, for the partial level of efficacy observed in the RV144 trial should provide important guidance to the field. This review discusses the ongoing HIV vaccine trials and also highlights recent scientific advances that have provided the field with new leads to invigorate the search for effective vaccines.