This study investigated the improvement in genetic evaluation of fertility traits by using production traits as secondary traits (MILK = 305-d milk yield, FAT = 305-d fat yield, and PROT = 305-d protein yield). Data including 471,742 records from first lactations of Denmark Holstein cows, covering the years of inseminations during first lactations from 1995 to 2004, were analyzed. Six fertility traits (i.e., interval in days from calving to first insemination, calving interval, days open, interval in days from first to last insemination, numbers of inseminations per conception, and nonreturn rate within 56 d after first service) were analyzed using single- and multiple-trait sire models including 1 or 3 production traits. Model stability was evaluated by correlation between EBV from 2 sub-data sets (DATA(A) and DATA(B)). Model predictive ability was assessed by the correlation between EBV from training data (DATA(A) or DATA(B)) and daughter performance (yield deviation, defined as average of daughter-records adjusted for nongenetic effects) from test data (DATA(B) or DATA(A)) in a cross-validation procedure, and correlation between EBV obtained from the whole data set (DATA(T)) and from a reduced data set (DATA(C1), which only contained the first crop daughters) for proven bulls. In addition, the superiority of the models was evaluated by expected reliability of EBV, calculated from the prediction error variance of EBV. Based on these criteria, the models combining milk production traits showed better model stability and predictive ability than single-trait models for all the fertility traits, except for nonreturn rate within 56 d after first service. The stability and predictive ability for the model including MILK or PROT were similar to the model including all 3 milk production traits and better than the model including FAT. In addition, it was found that single-trait models underestimated genetic trend of fertility traits. These results suggested that genetic evaluation of fertility traits would be improved using a multiple-trait model including MILK or PROT.