Proteins of fish muscle undergo chemical and physical changes during frozen storage which may result in, under certain conditions (i.e. long periods of storage, poor freezing practices, temperature fluctuations, etc), loss of quality, reflected mainly by an unacceptable texture as well as an undesirable flavour, odour and colour. In frozen gadoid fish species, most of these changes are caused by the production of formaldehyde in the muscle. Formaldehyde is produced, along with dimethylamine, by the enzymatic reduction of trimethylamine oxide (TMAO). Many aspects of formaldehyde production by TMAO demethylase (TMAOase) have been studied throughout the last decade. In addition, different approaches have been used to investigate the effect of formaldehyde production on protein denaturation and the associated muscle textural changes. Some insight into the reaction between protein and formaldehyde has clarified the possible mechanism of formaldehyde-mediated denaturation. However, evidence of covalent bonding between proteins and formaldehyde, to form crosslinks, has not explained fully the changes observed in fish proteins during frozen storage. The study of cold-induced denaturation of proteins might give new clues for further investigation of the problem. The implications of formaldehyde in toxicological and nutritional issues is also reviewed, as general concern about the safety of food products is a growing field in food science. Finally, different approaches have been proposed to avoid the detrimental action of formaldehyde during frozen storage of gadoid fish; they are some of the practical applications of the knowledge acquired after years of study of different workers in the field.