Freezing is one of the most commonly used techniques for long-term food storage, especially for perishable products. This study aimed to assess the effect of duration (3, 9 and 15 months) and temperature (−18, −45, and − 80 °C) of frozen storage on the physicochemical properties and microbiological status of vacuum-packed biceps femoris muscle of calves. Meat quality parameters, including pH, water activity, shear force, colour, degree of lipid oxidation, content of α-tocopherol and microbial count were measured. Storage duration was the primary factor influencing both physicochemical characteristics and microbiological quality. The optimal frozen storage for veal was 9 months. At this stage, the tenderness improved significantly (shear force decreased from 64.3 N at 72 h post mortem to 39.6 N; P < 0.05). The proportion of oxymyoglobin increased (55.59% vs. 80.50%; P < 0.05), whereas deoxymyoglobin decreased (33.86% vs. 7.47%; P < 0.05). The content of α-tocopherol remained stable (2.47 vs. 2.40 μg/g; P > 0.05), lipid oxidation was low (below 0.200 mg MDA/kg meat), and microbial counts (total viable counts, Enterobacteriaceae, Pseudomonas spp. and lactic acid bacteria) remained below the guideline values reported in the literature for raw beef (P > 0.05). These changes observed after 9 months were accompanied (already as from 3 months) by a significant reduction in water-holding capacity (up to 5.7% vs. purge loss 1.1% at 72 h post mortem; P < 0.05), and an increase in metmyoglobin (to 16.97% vs. 11.25%; P < 0.05). After 15 months of veal storage, marked adverse changes in comparison with 9 months were observed, including increased thaw loss (to 6.0%) and expressible water (to 65.8%), reduced oxymyoglobin (to 72.47%), a significant (P < 0.05) decrease in α-tocopherol (to 2.12 μg/g), and a significant deterioration of microbiological quality. However, even at that stage, all quality parameters of veal remained within acceptable limits. The freezing temperatures applied in the study did not significantly affect any microbiological counts or most physicochemical properties.