Extrapair paternity (EPP) is purported to be an important contributor to the evolution of plumage dimorphism, and yet relatively few studies have demonstrated that EPP creates selection pressures on male traits. Sexual size dimorphism (SSD) is instead typically assumed to have evolved in association with polygyny rather than EPP. Yet, the New Zealand tui, Prosthemadera novaeseelandiae, is a socially monogamous passerine exhibiting extreme SSD and sexual plumage dimorphism. Here, we examine whether EPP has contributed to the evolution of SSD in body size and ornament size in the tui. We discovered one of the highest rates of EPP currently known, with extrapair young occurring in 72% of broods and accounting for 57% of all offspring. Both male body size and ornament size were strongly correlated to EPP, with within-pair paternity success positively related to both traits. Male ornament size, but not body size, was a significant predictor of a male's success at siring extrapair offspring. Although these patterns may have arisen through either male-male competition or female choice, it is likely that these 2 mechanisms are not mutually exclusive in tui. This study provides evidence that EPP can both create selection pressures on male traits, and contribute to the evolution of SSD.