© 2015, American Society for Microbiology. HLA-B*13 is associated with superior in vivo HIV-1 viremia control. Protection is thought to be mediated by sustained targeting of key cytotoxic T lymphocyte (CTL) epitopes and viral fitness costs of CTL escape in Gag although additional factors may contribute. We assessed the impact of 10 published B*13-associated polymorphisms in Gag, Pol, and Nef, in 23 biologically relevant combinations, on HIV-1 replication capacity and Nef-mediated reduction of cell surface CD4 and HLA class I expression. Mutations were engineered into HIV-1NL4.3, and replication capacity was measured using a green fluorescent protein (GFP) reporter T cell line. Nef-mediated CD4 and HLA-A*02 downregulation was assessed by flow cytometry, and T cell recognition of infected target cells was measured via coculture with an HIV-specific luciferase reporter cell line. When tested individually, only Gag- I147L and Gag-I437L incurred replicative costs (5% and 17%, respectively), consistent with prior reports. The Gag-I437L-mediated replication defect was rescued to wild-type levels by the adjacent K436R mutation. A novel B*13 epitope, comprising 8 residues and terminating at Gag147, was identified in p24Gag (GQMVHQAIGag140-147). No other single or combination Gag, Pol, or Nef mutant impaired viral replication. Single Nef mutations did not affect CD4 or HLA downregulation; however, the Nef double mutant E24Q-Q107R showed 40% impairment in HLA downregulation with no evidence of Nef stability defects. Moreover, target cells infected with HIV-1-NefE24Q-Q107R were recognized better by HIV-specific T cells than those infected with HIV-1NL4.3 or single Nef mutants. Our results indicate that CTL escape in Gag and Nef can be functionally costly and suggest that these effects may contribute to long-term HIV-1 control by HLA-B*13.