The aim of this work was to evaluate the effects of freezing and frozen storage at –24 °C on the quality of Icelandic herring fillets, focusing on protein solubility and viscosity at pH 2.7 and 11 used for pH-aided protein isolation. The evaluation of quality was based on chemical analyses, protein degradation measurements, and changes in protein solubility and viscosity at pH 2.7 and 11 after up to 6-mo frozen storage of the herring fillets. Lipid oxidation measured as TBARS values increased significantly during the frozen storage (P < 0.05). Protein solubility at pH 2.7 decreased during frozen storage for 6 mo, where the solubility was about 10% lower after 6-mo frozen storage compared to the beginning (P < 0.05). At pH 11, the solubility became approximately 15% lower after 6-mo frozen storage compared to initial solubility (P < 0.05). Viscosity, measured at pH 2.7, increased after 3 mo of frozen storage (P < 0.05). At pH 11, the viscosity increased significantly after 1-wk frozen storage, compared to fresh herring fillets, but did not increase significantly with further storage (P < 0.05). Changes found in solubility and viscosity indicated protein degradation due to freezing and frozen storage. SDS-PAGE analysis did not reveal any protein cross-linking or aggregation formation, either with frozen storage or due to exposure to low pH.