While considerable variations in both the frequency of extra-pair paternity (EPP) and the behavioral events that produce it are recognized among species, populations, individuals, and breeding attempts, the determinants of these variations are surprisingly difficult to establish. Nest predation may be one such determinant, since it is the most important source of reproductive failure, and past studies have suggested a variety of reproductive flexibilities under nest predation risk. However, despite its potentially significant effect on mating behaviors, nest predation risk has rarely been discussed in association with variations in intraspecific EPP patterns. Here, we examined the effect of naturally occurring nest predation, which varied between sites, years, and breeding attempts, on patterns of EPP in 92 broods (132 adults and 710 nestlings) of the Japanese great tit Parus major minor. We found that the frequency of extra-pair offspring was positively correlated with the nest predation rate, along with a correlation to breeding attempts in a season, but not with other factors such as individual quality or breeding density. Under high nest-predation risk, it may be adaptive for males to search for additional extra-pair copulation to spread the risk of losing all offspring and to invest less in mate-guarding, which also enables females to seek additional extra-mating. The results of this study suggest that nest predation risk, among other factors, may significantly influence paternity allocation in birds.