Hosts may mitigate the impact of parasites by two broad strategies: resistance, which limits parasite burden, and tolerance, which limits the fitness or health cost of increasing parasite burden. The degree and causes of variation in both resistance and tolerance are expected to influence host-parasite evolutionary and epidemiological dynamics and inform disease management, yet very little empirical work has addressed tolerance in wild vertebrates. Here, we applied random regression models to longitudinal data from an unmanaged population of Soay sheep to estimate individual tolerance, defined as the rate of decline in body weight with increasing burden of highly prevalent gastrointestinal nematode parasites. On average, individuals lost weight as parasite burden increased, but whereas some lost weight slowly as burden increased (exhibiting high tolerance), other individuals lost weight significantly more rapidly (exhibiting low tolerance). We then investigated associations between tolerance and fitness using selection gradients that accounted for selection on correlated traits, including body weight. We found evidence for positive phenotypic selection on tolerance: on average, individuals who lost weight more slowly with increasing parasite burden had higher lifetime breeding success. This variation did not have an additive genetic basis. These results reveal that selection on tolerance operates under natural conditions. They also support theoretical predictions for the erosion of additive genetic variance of traits under strong directional selection and fixation of genes conferring tolerance. Our findings provide the first evidence of selection on individual tolerance of infection in animals and suggest practical applications in animal and human disease management in the face of highly prevalent parasites.