The ability of compounds of natural origin (black, white, red, and green tea extracts, phytic acid) to inhibit TMAO-demethylase enzyme was assayed. Black tea and phytic acid exerted the highest inhibiting activities, similar to the already known inhibitor sodium citrate. Hake minces incorporating these three compounds were prepared and stored frozen (150 days, -12 °C). TMAO-demethylase enzyme was partially inhibited (lower enzyme activity, reduction of formaldehyde accumulation). The study of physicochemical properties of the minces (salt-soluble proteins, water holding capacity, structural water associated with myofibrils) pointed to evident protein aggregation and loss of functionality when phytic acid was added, whereas black tea and sodium citrate did not have a negative effect. Consequently, the salt-ground mince with phytic acid showed worse viscoelastic properties than the others. In conclusion, black tea polyphenols and sodium citrate can be used as additives to inhibit TMAO-demethylase enzyme during frozen storage of fish minces.