Multivariate data analysis has been combined with proteomics to enhance the recovery of information from 2-DE of cod muscle proteins during different storage conditions. Proteins were extracted according to 11 different storage conditions and samples were resolved by 2-DE. Data generated by 2-DE was subjected to principal component analysis (PCA) and discriminant partial least squares regression (DPLSR). Applying PCA to 2-DE data revealed the samples to form groups according to frozen storage time, whereas differences due to different storage temperatures or chilled storage in modified atmosphere packing did not lead to distinct changes in protein pattern. Applying DPLSR to the 2-DE data enabled the selection of protein spots critical for differentiation between 3 and 6 months frozen storage with 12 months frozen storage. Some of these protein spots have been identified by MS/MS, revealing myosin light chain 1, 2 and 3, triose-phosphate isomerase, glyceraldehyde-3-phosphate dehydrogenase, aldolase A and two alpha-actin fragments, and a nuclease diphosphate kinase B fragment to change in concentration, during frozen storage. Application of proteomics, multivariate data analysis and MS/MS to analyse protein changes in cod muscle proteins during storage has revealed new knowledge on the issue and enables a better understanding of biochemical processes occurring.