Frozen mandarin fish (MF) is utilized for preparation fermented MF. However, how raw material (RM) affects the quality and flavor of fermented MF is unclear. This study investigated the impact and mechanism of RM frozen storage on the microstructure, texture, water distribution, and flavor of fermented MF by light microscopy, texture profile analysis, low-field nuclear magnetic resonance, gas chromatography-ion mobility spectrometry, and multivariate analysis. With increasing RM frozen storage time, both frozen MF and frozen-based fermented MF decreased in muscle fiber density while increased in muscle fiber diameter. Additionally, RM frozen storage exhibited a significant impact on the water distribution of frozen MF, while no obvious effect on that of frozen-based fermented MF. Seven odorant (2-methyl-1-propanol, 3-hydroxy-2-butanone, 2,3-butanedione, hexanal-D, ethyl acetate-D, 3-pentanone, and acetone) were shown as potential markers to distinguish fermented MF. This study could provide a theoretical basis for the production of high-quality frozen-based fermented MF.