This study was designed to estimate genetic parameters for the following traits of Brahman cattle in Brazil: age at first calving (AFC), calving interval (CI), rebreeding (REB), and stayability (STAY). The data were provided by Brazilian Association of Zebu Breeders (ABCZ), and included Brahman cattle that were born between 1994 and 2012. For REB, the value 1 was assigned to heifers that rebreed and calved after first calving, and the value 0 was assigned to heifers that failed to rebreed after first calving. Likewise, for STAY, the value 1 was assigned to heifers that calved at least 3 times when they were 6-yr-old; otherwise, the value 0 was assigned. We utilized bivariate analysis using linear-threshold animal model to estimate co-variances components by using the software GIBBSF90 and THRGIBBS1F90 from BGF90. The model included fixed effects, random effects that represented additive genetic direct effects of each animal, permanent environmental effects, included as random, and residuals. For AFC and STAY, the fixed effects were composed only by contemporary group. Besides that, for REB and CI, the fixed effects were composed by contemporary group, calf birth year and calf birth season. Also, the covariate dam age at calving was included for CI. The permanent environmental effects only were included in the model for CI. The contemporary groups were composed from farm, type of gestation (AI or natural service) and birth year of dam; and in addition, only for STAY, birth season of dam (rainy or dry). The mean h² were 0.10, 0.02, 0.22, and 0.10 for AFC, CI, REB, and STAY; respectively. The genetic correlations were −0.13 between AFC and CI, −0.35 between AFC and REB, −0.57 between AFC and STAY, and 0.32 between REB and STAY, which reveal that cows that remain productive for longer periods in the herd, also start breeding younger and present greater chances to REB; however, heifers that calved too young may present problems, such as calving difficulty, that may increase CI. The selection of Brahman cattle for reproductive traits, such as AFC, CI, REB, and STAY, will render low magnitude and long-term responses.