Hepatocellular carcinoma (HCC) is one of the most common malignancies over the world. Alpha-fetoprotein (AFP) is an oncofetal protein during HCC development that could generate weaker and less reproducible antitumor protection, and it may serve as a target for immunotherapy. Therefore, it is imperative to enhance its immunogenicity and develop therapeutic vaccines to eliminate AFP-expressing tumors. In this study, by way of glutaraldehyde cross-linking, we constructed a potential therapeutic protein complex vaccine, heat shock protein 72 (HSP72)/AFP. Our results demonstrated that AFP and HSP72 synergistically exhibited significant increases in AFP-specific CD8(+) T cell responses and impressive antitumor effects against AFP-expressing tumors. Priming mice with the reconstructed vaccine, we elicited robust strong protective immunity. Our study suggests that a tumor vaccine by cross-linking tumor antigen and HSP72 is a promising approach for cancer therapy.