Background: Costs of adaptation play an important role in host-parasite coevolution. For parasites, evolving the ability to circumvent host resistance may trade off with subsequent growth or transmission. Such costs of virulence (sensu plant pathology) limit the spread of all-infectious genotypes and thus facilitate the maintenance of genetic polymorphism in both host and parasite. We investigated costs of three virulence factors in Puccinia striiformis f.sp.tritici, a fungal pathogen of wheat (Triticum aestivum). Results: In pairwise competition experiments, we compared the fitness of near-isogenic genotypes that differed by a single virulence factor. Two virulence factors (vir4, vir6) imposed substantial fitness costs in the absence of the corresponding resistance genes. In contrast, the vir9 virulence factor conferred a strong competitive advantage to several isolates, and this for different host cultivars and growing seasons. In part, the experimentally derived fitness costs and benefits are consistent with frequency changes of these virulence factors in the French pathogen population. Conclusion: Our results illustrate the variation in the evolutionary trajectories of virulence mutations and the potential role of compensatory mutations. Anticipation of such variable evolutionary outcomes represents a major challenge for plant breeding strategies. More generally, we believe that agro-patho-systems can provide valuable insight in (co)evolutionary processes in host-parasite systems.