The influence of major histocompatibility complex class I (MHC-I) alleles on human immunodeficiency virus (HIV) diversity in humans has been well characterized at the population level. MHC-I alleles likely affect viral diversity in the simian immunodeficiency virus (SIV)-infected pig-tailed macaque (Macaca nemestrina) model, but this is poorly characterized. We studied the evolution of SIV in pig-tailed macaques with a range of MHC-I haplotypes. SIVmac251 genomes were amplified from the plasma of 44 pig-tailed macaques infected with SIVmac251 at 4 to 10 months after infection and characterized by Illumina deep sequencing. MHC-I typing was performed on cellular RNA using Roche/454 pyrosequencing. MHC-I haplotypes and viral sequence polymorphisms at both individual mutations and groups of mutations spanning 10-amino-acid segments were linked using in-house bioinformatics pipelines, since cytotoxic T lymphocyte (CTL) escape can occur at different amino acids within the same epitope in different animals. The approach successfully identified 6 known CTL escape mutations within 3 Mane-A1*084-restricted epitopes. The approach also identified over 70 new SIV polymorphisms linked to a variety of MHC-I haplotypes. Using functional CD8 T cell assays, we confirmed that one of these associations, a Mane-B028 haplotype-linked mutation in Nef, corresponded to a CTL epitope. We also identified mutations associated with the Mane-B017 haplotype that were previously described to be CTL epitopes restricted by Mamu-B*017:01 in rhesus macaques. This detailed study of pig-tailed macaque MHC-I genetics and SIV polymorphisms will enable a refined level of analysis for future vaccine design and strategies for treatment of HIV infection.