Because of the importance of reproduction in stock breeding systems, it is necessary to find selection criteria that increase reproductive efficiency. The aim of this study was to estimate genetic parameters for the probability of conception on first service (PROB) in Murrah heifers, and its association with other traits of economic interest [age at first calving (AFC), service period, calving interval and milk yield at 270 days], with the purpose of evaluating their use as selection criteria. Reproductive information and first lactation records of 1200 Murrah heifers were used to perform two-trait analyses between PROB and the other characteristics. Bayesian inference was used to estimate the variance components, considering PROB as threshold and the other as linear factors. The results demonstrate that this trait has heritability of 0.15, indicating the possibility of a genetic gain by using it for selection. With respect to the genetic correlation estimates, the only high-magnitude association was with AFC (−0.899), which is the current criterion indicating sexual precocity of females. In the light of the parameters estimated, the first-service pregnancy rate is an alternative for indication of sexual precocity, although presenting a smaller genetic gain than the current standard AFC. Nevertheless, additional research should be conducted regarding this trait to assess the economic importance of its use in dairy buffalo production systems.