Cholesterol oxidation products (COPs) in foods may pose risks for human health. Suitable antioxidants can reduce the formation of COPs in industrial products. Consumer awareness of food additives has brought a need for more natural alternatives. This is the first study on the effects of supercritical CO2 extracts of rosemary, oregano, and an antimicrobial blend of seven herbs, tested at two levels (1 and 3 g/kg fish), against cholesterol oxidation in patties made of a widely consumed fish species, Atlantic salmon (Salmo salar), during baking and storage. Cholesterol oxidation was reduced by the extracts as indicated by lowered levels of 7α-hydroxycholesterol, 7β-hydroxycholesterol, and 7-ketocholesterol, which were quantified by GC-MS. The total amount of COPs was smaller in all of the cooked samples containing the plant extracts (<1 μg/g extracted fat) than in the cooked control (14 μg/g). Furthermore, the plant extracts exhibited protective effects also during cold storage for up to 14 days.