Adaptive explanations for the evolution of extra-pair paternity (EPP) suggest that females seek extra-pair copulations with high quality males. Still, the link between ornamentation, individual quality and paternity remains unclear. Moreover, honest signaling is essential when explaining EPP because it is needed for sexual selection to occur; yet, it is understudied in multiple ornaments. Because blue tits (Cyanistes caeruleus) show variable color expression in several plumage patches, we tested: (i) over two seasons, whether males in better condition, more ornamented and less infected by blood parasites gain EPP and have higher reproductive success, and (ii) over three seasons, whether mating patterns affect color change. Males with more saturated yellow feathers, brighter tails and in better condition had higher reproductive success in one of the seasons. Contrary to expectation, in another season, males that gained EPP were parasitized by blood parasites, suggesting increased vector exposure during extra-pair copulations. Our results for two seasons show that males siring more extra-pair young were older and grew brighter cheek or tail feathers for the following season. Despite the increased mating costs, in socially monogamous avian systems, high quality males incur in EPP without compromising traits that may be under sexual selection.