Despite the tremendous efforts to develop a successful human immunodeficiency virus (HIV) vaccine, the quest for a safe and effective HIV vaccine seems to be remarkably long and winding. Disappointing results from previous clinical trials of VaxGen's AIDSVAXgp120 vaccine and MRKAd5 HIV-1 Gag/Pol/Nef vaccine emphasize that understanding the correlates of immune protection in HIV infection is the key to solve the puzzle. The modest vaccine efficacy from RV144 trial and the successive results obtained from the correlate of risk analysis have reinvigorated the HIV vaccine research field leading to various novel strategies. This paper will review the brief history and recent advances in HIV vaccine development.