In this study, a key unresolved challenge for developing an effective HIV-1 vaccine is the discovery of strategies to elicit immune responses that are able to cross-protect against a significant fraction of the diverse viruses that are circulating worldwide. Here, we summarize some of the immunological implications of HIV-1 diversity, and outline the rationale behind several polyvalent vaccine design strategies that are currently under evaluation. Vaccine-elicited T-cell responses, which contribute to the control of HIV-1 in natural infections, are currently being considered in both prevention and treatment settings. Approaches now in preclinical and human trials include full proteins in novel vectors, concatenated conserved protein regions, and polyvalent strategies that improve coverage of epitope diversity and enhance the cross-reactivity of responses. While many barriers to vaccine induction of broadly neutralizing antibody (bNAb) responses remain, epitope diversification has emerged as both a challenge and an opportunity. Recent longitudinal studies have traced the emergence of bNAbs in HIV-1 infection, inspiring novel approaches to recapitulate and accelerate the events that give rise to potent bNAb in vivo. In this review, we have selected two such lineage-based design strategies to illustrate how such in-depth analysis can offer conceptual improvements that may bring us closer to an effective vaccine.