Recurrent Staphylococcus aureus infections are common, despite robust immune responses. S. aureus infection elicited protective antibody and T cell responses in mice that expressed the Major Histocompatibility Complex (MHC) of the H-2^d haplotype, but not H-2^b, demonstrating that host genetics drives individual variability. Vaccination with a-toxin or leukotoxin E (LukE) elicited similar antibody and T cell responses in mice expressing H-2^d or H-2^b, but vaccine-elicited responses were inhibited by concomitant infection in H-2^d–expressing mice. These findings suggested that competitive binding of microbial peptides to host MHC proteins determines the specificity of the immunodominant response, which was confirmed using LukE-derived peptide-MHC tetramers. A vaccine that elicited T cell and antibody responses protected mice that expressed H-2^d or H-2^b, demonstrating that vaccination can overcome MHC-restricted immunodominance. Together, these results define how host genetics determine whether immunity elicted by S. aureus is protective and provide a mechanistic roadmap for future vaccine design.