Within a population of Charolais young bulls, two extreme groups of longissimus thoracis muscle samples, classified according to Warner−Bratzler shear force (WBSF) of 55 °C grilled meat, were analyzed by 2D-electrophoresis. Muscle analyses were performed on 4 bulls of the “tender” group (WBSF = 27.7 ± 4.8 N) and 4 bulls of the “tough” group (WBSF = 41.2 ± 6.1 N), at 3 post-mortem times: D0, samples taken within 10 min post-mortem; D5 and D21, samples kept at 4 °C under vacuum during 5 and 21 days. Proteins of muscle samples were separated in two fractions based on protein solubility in Tris buffer: “soluble” and “insoluble”. Proteins of both fractions were separated by 2D-electrophoresis. Evolution of spots during the 3 post-mortem times was analyzed by hierarchical classification (HCA). Three clusters of proteins presenting similar evolution profiles provided accurate classification of post-mortem times and showed the translocation of some chaperone proteins and glycolytic enzymes from the soluble fraction to the insoluble fraction between D0 and D5. Cellular structure dismantlement and proteolysis was observed at D21. Effect of group (“tender” vs “tough”) on spot intensities was tested by ANOVA. At D0, higher quantity of proteins of the inner and outer membrane of mitochondria was found in the tender group suggesting a more extensive degradation of mitochondria that may be related to the apoptotic process.