To estimate heritability (h2) for yearling heifer pregnancy and to estimate the genetic correlation between heifer pregnancy and scrotal circumference, 18,145 records of Nellore heifers exposed to breeding at an age of approximately 14 mo and 25,466 records of contemporary young bulls were analyzed. Heifer pregnancy was considered as a categorical trait, with the value 1 (success) assigned to heifers that were pregnant after rectal palpation approximately 60 d after the end of a 90-d breeding season and the value 0 (failure) otherwise. A single-trait animal model for heifer pregnancy and a two-trait animal model including heifer pregnancy and scrotal circumference were used. Contemporary groups were defined in two ways: including (CG2) or not including (CG1) weaning management of the heifer. Heritability estimates obtained by Method R in single-trait analyses were 0.68 +/- 0.09 and 0.61 +/- 0.10 using CG1 and CG2 definitions, respectively. Heritability estimates for two-trait analyses were 0.69 +/- 0.09 (CG1) and 0.63 +/- 0.08 (CG2) for heifer pregnancy and 0.57 +/- 0.03 (both CG) for scrotal circumference. The genetic correlation estimates between the two traits were 0.20 +/- 0.12 (CG1) and 0.20 +/- 0.13 (CG2). Based on the results of this study, EPD for heifer pregnancy can be used to select bulls for the production of precocious daughters and will be more effective than selecting on scrotal circumference EPD in Nellore cattle. However, scrotal circumference can be incorporated in a two-trait analysis to increase the accuracy of prediction for heifer pregnancy EPD for young bulls. Using contemporary group without heifer weaning management gave higher h2 and, for two-trait analysis, converged more quickly.