Genetic parameters, genetic trends, and genetic progress of carcass traits were estimated for 12,447 Nellore individuals from different Brazilian herds. The following carcass traits were analyzed: visual body scores of conformation (CONF), precocity (PREC), and muscularity (MUSC); rump width (RW) and rump length (RL), body size (frame); and ultrasound evaluation of ribeye area (REA), backfat thickness (BFT), and rump fat thickness (RFT). Heritability estimates (± SE) for CONF, PREC, and MUSC were 0.23 ± 0.02, 0.33 ± 0.03, and 0.31 ± 0.02, respectively. The heritability estimates (± SE) for RW, RL, and frame were 0.25 ± 0.05, 0.16 ± 0.04, and 0.31 ± 0.03, respectively. Ultrasound of the REA, BFT, and RFT presented mean heritability estimates (± SE) of 0.38 ± 0.03, 0.44 ± 0.04, and 0.47 ± 0.04, respectively. The visual body score of CONF had high genetic correlations with RW, RL, and frame (0.74 ± 0.09, 0.82 ± 0.08, and 0.83 ± 0.04, respectively), indicating a high association of CONF with the measurements related to body structure. The REA had no correlation with BFT and RFT (-0.09 ± 0.04 and -0.03 ± 0.04, respectively) and showed only a moderate genetic correlation with MUSC (0.39 ± 0.05). The BFT and RFT had moderate genetic correlations with PREC (0.36 ± 0.07 and 0.29 ± 0.07, respectively) and no correlation with frame (-0.02 ± 0.03 and 0.05 ± 0.05, respectively), suggesting that selection for frame had no effect on the subcutaneous fat content of the carcass. Low genetic trends and low genetic progress were obtained for REA (0.026 cm, 0.02%), BFT (0.0031 mm, 0.05%), and RFT (0.0013 mm, 0.02%), with no significant values of genetic progress detected throughout the studied period. The CONF, PREC, and MUSC presented high genetic trends (0.030 points, 0.030 points, and 0.029 points, respectively) and high genetic progress (0.60%, 0.56%, and 0.59%, respectively), indicating a significant genetic progress for these traits throughout the evaluated period. Carcass traits evaluated by ultrasound and visual body scores are eligible for selection and can be used in genetic improvement programs in Nellore cattle; however, visual body score selection for carcass traits can result in slower genetic progress for carcass quality when compared to selection performed by ultrasound.