Proteomics has been widely used to study muscle biology and meat quality traits from different species including beef. Beef proteomics studies allow a better understanding of the biological processes related to meat quality trait determination. This study aimed to decipher by means of two-dimensional electrophoresis (2D-PAGE), mass spectrometry and bioinformatics the changes in post-mortem muscle with a focus on proteins differentially expressed in the Longissimus thoracis (LT) muscle of immunocastrated young heifers and steers. Carcass traits, chemical composition, pH, instrumental color (L*, a*, b*), cooking loss and Warner-Bratzler shear force (WBSF) of meat from F1 Montana-Nellore cattle were also evaluated. Backfat thickness (BFT) and intramuscular fat content (IMF) were 46.8% and 63.6% higher in heifers (p < 0.05), respectively, while evaporation losses (EL) were 10.22% lower compared to steers. No differences (p > 0.05) were observed for tenderness evaluated by WBSF (3, 10, and 17 days post-mortem), pH, and color traits (L*, a* and b*) between the experimental groups. The study revealed several proteins to be differentially expressed proteins in heifers compared steers (p < 0.05). In heifers, proteins involved in nutrient transport (TF, ALB, and MB), energy metabolism (ALDOA, GAPDH, and PKM), and oxidative stress and response to stress (HSPA8 and CA3) were associated with a greater BFT and IMF deposition. The higher expression of these proteins indicated greater oxidative capacity and lower glycolytic activity in the LT muscle of heifers. In steers, there was greater abundance of protein expression related to muscle contraction and proteins of structure (ACTA1, TPM2 and TNNT3), energy metabolism (ENO1, ENO3, PYGM, PGM1 and TPI1) and ATP metabolism (ATP5F1B, PEBP1 and AK1), indicating greater glycogenolysis in LT muscle, suggesting a shift in the glycolytic/oxidative fibers of steers.