Although the frequency of extra-pair paternity (EPP) has been described for many species, the relative importance of the various contemporary and historical factors explaining EPP variation is still the subject of debate. In this study, we found 11 polymorphic microsatellite loci in the Savi's Warbler (Locustella luscinioides), and used eight loci to analyze the paternity of 392 nestlings belonging to 102 broods of this little-known species. The frequency of EPP was 4.1% of nestlings and 5.9% of broods, which is surprisingly low given what is known about Savi's Warbler's life history and ecology, and among the lowest found of any socially-monogamous passerine bird. Comparisons with similar species indicate that this low frequency is unlikely to have been determined by the ancient evolution of life history strategies. Our observations suggest that the costs of engaging in extra-pair copulations might be high for the females. Larger males, particularly those with longer bill and tarsus, are more likely to be cuckolded; and the few possible comparisons between cuckolded males and extra-pair sires reveal a similar pattern. We further show that bill and tarsus lengths correlate with arrival date, which is associated with individual quality in many migratory bird species.