Human cytomegalovirus (HCMV) infection, the most common cause of congenital disease globally, affecting an estimated 1 million newborns annually, can result in lifelong sequelae in infants, such as sensorineural hearing loss and brain damage. HCMV infection also leads to a significant disease burden in immunocompromised individuals. Hence, an effective HCMV vaccine is urgently needed to prevent infection and HCMV-associated diseases. Unfortunately, despite more than five decades of vaccine development, no successful HCMV vaccine is available. This review summarizes what we have learned from acquired natural immunity, including innate and adaptive immunity; the successes and failures of HCMV vaccine human clinical trials; the progress in related animal models; and the analysis of protective immune responses during natural infection and vaccination settings. Finally, we propose novel vaccine strategies that will harness the knowledge of protective immunity and employ new technology and vaccine concepts to inform next-generation HCMV vaccine development.