Successful vaccine development for infectious diseases has largely been achieved in settings where natural immunity to the pathogen results in clearance in at least some individuals. HIV presents an additional challenge in that natural clearance of infection does not occur, and the correlates of immune protection are still uncertain. However, partial control of viremia and markedly different outcomes of disease are observed in HIV-infected persons. Here, we examine the antiviral mechanisms implicated by one variable that has been consistently associated with extremes of outcome, namely HLA class I alleles, and in particular HLA-B, and examine the mechanisms by which this modulation is likely to occur and the impact of these interactions on evolution of the virus and the host. Studies to date provide evidence for both HLA-dependent and epitope-dependent influences on viral control and viral evolution and have important implications for the continued quest for an effective HIV vaccine.