Song is a sexually selected trait in many bird species and has been suggested to function as a signal of a male's health and parasite resistance. Here we present an experimental field study on the long-term effects of parasite exposure early in life on adult bird song. We exposed nestling great tits (Parus major) to ectoparasitic hen fleas (Ceratophyllus gallinae) and on their recruitment into the local breeding population assessed the response to a playback of a challenging male in their breeding territory. We show, to our knowledge for the first time in a wild bird population, that parasite exposure early in life affects bird song: song duration of males that were exposed to parasites early in life was reduced by 32% compared with males that grew up in a flea-free environment. Early parasite exposure also significantly reduced the degree of song overlap with the playback, which has been shown to correlate with social status. There was no effect of early parasite exposure on the number of different song types sung or on the latency until the males started the vocal response to the playback. These results suggest that mates or rivals can use song duration and song overlap as proxies for an individual's exposure to parasites early in life. It thereby highlights both the importance of parasites in maintaining honesty of sexually selected traits and the costs of parasitism in terms of reduced attractiveness and competitiveness.