Different chilled (~0.1 °C for up to 5 weeks) then frozen storage (up to 12 months) combinations and two frozen storage holding temperatures (−12 °C and −18 °C) effects on beef M. longissimus lumborum (LL) protein structure degradation and a marker of protein oxidation were tested. Particle size (PS) analysis and protein solubility results found storage combination effects on protein degradation to be significant (P < 0.05), although the influence of frozen holding temperatures was negligible. LL carbonyl, and nitrate and nitrite content responses were variable and yet broadly reflected an increased incidence of protein oxidation across increasing chilled storage and ensuing frozen storage periods – this aspect meriting future exploration. Total myoglobin content and the estimated myoglobin redox fractions (metmyoglobin, deoxymyoglobin, and oxymyoglobin) were also subject to storage treatment. These findings demonstrate the capacity for beef storage selection (chilled-then-frozen) to manage compositional protein changes and its implications on sensory quality traits across comparative ‘long term’ durations.