Background: Coevolution between pairs of different kind of entities, such as providers and users of information, involves reciprocal selection pressures between them as a consequence of their ecological interaction. Pied flycatchers ( Ficedula hypoleuca ) have been shown to derive fitness benefits (larger clutches) when nesting in proximity to great tits ( Parus major ), presumably because they this way discover and obtain information about nesting sites. Tits suffer from the resulting association (smaller clutches). An arms race between the tits (information host) and the flycatchers (information parasite) could thus result . Great tits often cover eggs with nesting material before, but not during incubation. We hypothesized that one function of egg-covering could be a counter-adaptation to reduce information parasitism by pied flycatchers. We predicted that tits should bring more new hair to cover their exposed eggs when a pied flycatcher is present near to tit nest than when a neutral (non-competing) species is present. We conducted decoy and playback experiment in Oulu and Turku, Finland. First, we removed and collected all the hair covering the tit eggs. Then, we measured how the perceived presence of flycatcher or waxwing ( Bombycilla garrulus ) affects tits' egg-covering by collecting and weighing the hair brought on the eggs and photographing the nest 24 h after the playback. Results: Tits brought more hair into the nest and covered the eggs more carefully after flycatcher treatment, compared to waxwing treatment. We also found that the tits in Oulu (over 600 km to north from Turku) had more hair on the top of their eggs in general. Conclusions: Together, these results suggest that the counter-adaptation function of egg-covering against information parasites may be an extension of original function to protect eggs from low temperatures.