Immune memory evolved to protect hosts from reinfection, but incomplete responses that allow future reinfection might inadvertently select for more harmful pathogens. We present empirical and modeling evidence that incomplete immunity promotes the evolution of higher virulence in a natural host-pathogen system. We performed sequential infections of house finches with Mycoplasma gallisepticum strains of varying virulence. Virulent bacterial strains generated stronger host protection against reinfection than less virulent strains, and thus excluded less virulent strains from infecting previously-exposed hosts. In a two-strain model, the resulting fitness advantage selected for an almost two-fold increase in pathogen virulence. Thus, the same immune systems that protect hosts from infection can concomitantly drive the evolution of more harmful pathogens in nature.