Consumption of fish is rapidly increasing worldwide. It is important to evaluate fish fillet quality because fish undergoes physical and chemical changes during frozen storage. Fish fillets exhibit formaldehyde (FA) accumulation from the decomposition of trimethylamine N-oxide. FA is a powerful protein denaturant; thus, it is important to avoid FA buildup during fish processing to preserve fish quality, especially texture. To determine where FA accumulates, in order to maintain the quality of fish fillets, we performed matrix-assisted laser desorption/ionization mass spectrometry imaging, aiming to identify muscle-derived peptides, which reflect conditions such as denaturation and/or aggregation. We used frozen sections from which lipophilic molecules were washed out and detected various peptide peaks. Furthermore, we tried to identify indices to represent fish fillet softening by protease treatment. We could detect characteristic peaks owing to FA and protease treatment; the findings were consistent with the results of texture profiles showing fish fillet’s real solidity. These molecules might thus serve as effective markers to evaluate fish fillet quality.