Mutationally constrained epitopes of variable pathogens represent promising targets for vaccine design but are not reliably identified by sequence conservation. In this study, we employed structure-based network analysis, which applies network theory to HIV protein structure data to quantitate the topological importance of individual amino acid residues. Mutation of residues at important network positions disproportionately impaired viral replication and occurred with high frequency in epitopes presented by protective human leukocyte antigen (HLA) class I alleles. Moreover, CD8(+) T cell targeting of highly networked epitopes distinguished individuals who naturally control HIV, even in the absence of protective HLA alleles. This approach thereby provides a mechanistic basis for immune control and a means to identify CD8(+) T cell epitopes of topological importance for rational immunogen design, including a T cell-based HIV vaccine.