Thermal inactivation of peroxidase (POD) and lipoxygenase (LOX), both enzymes present in broccoli and Brussels sprouts, is required before freezing, to obtain high-quality precooked frozen vegetables. Rate constants of a 1st-order biphasic model for the heat-labile and heat-resistant POD and LOX isoenzymes were determined at different temperatures (75, 80, and 90 °C) and the corresponding activation energies were estimated using nonlinear regressions. In the case of Brussels sprouts, the activation energies for the resistant and labile fractions were 56.3 and 62.5 kJ/mol for POD and 63.7 and 65.8 kJ/mol for LOX, respectively. For Brussels sprouts, different precooking times were tested to analyze the effect of residual enzyme activity on quality parameters and sensory attributes, after a frozen storage of 4 mo at −20 °C. A significant reactivation of enzyme activity after frozen storage was observed (especially in the case of POD) for short precooking times (<6 min) leading to low-quality parameters at the interior zone of the vegetable. A precooking time of 6 min at 90 °C allowed an adequate inactivation of LOX and POD obtaining a high-quality final frozen vegetable. A sensory analysis confirmed the global acceptability of the product. The obtained results are relevant to define the precooking stage conditions in the production of frozen cruciferous vegetables.