This explorative study aimed to assess the mutagenicity and genotoxicity of stored-cooked beef patties formulated with and without phenols (7.00 mg of phenols/80-g patty) extracted from olive vegetation water (OVW), as related to the formation of cholesterol oxidation products (COPs) and heterocyclic amines (HCAs). The patties were packaged in a modified atmosphere, sampled during cold storage (4 °C) for 9 days, and grilled at 200 °C. The genotoxicity was evaluated by the Comet assay. The patty extract was found to be genotoxic on primary peripheral blood mononuclear cells (PBMCs), while no mutagenicity was detected. The addition of OVW phenols significantly decreased the genotoxicity of the patty extract and reduced the total COPs content in stored-cooked patties (4.59 times lower than control); however, it did not affect the content of total HCAs (31.51–36.31 ng/patty) and the revertants’ number. Therefore, these results demonstrate that the OVW phenols were able to counteract the formation of genotoxic compounds in stored-cooked beef patties.