Proteins play a substantial role in the deterioration of partial freezing shrimp product quality. In this study, traditional protein indicators were used to determine changes in shrimp muscle quality during storage, and the changed proteins were identified using proteomic analysis. The decrease in total sulfhydryl (SH) content and the increase in carbonyl content indicate protein is denatured. The decrease in Ca2+-ATPase activity and the increase in surface hydrophobicity also indicate protein denatured. The increase of hydrophobic interaction and disulfide bonds suggest a larger and closer network among proteins. A total of eight changed protein bands were detected on sodium dodecyl sulfate-polyacrylamide gel electrophoresis (SDS-PAGE) diagram under partial freezing storage. Three of them were identified as α-actinin (97 kDa), invertebrate connectin (I-connectin (55 kDa)), and troponin I (30 kDa), respectively, which are essential components of myofibrillar protein. The results of the bioinformatic analysis showed that α-actinin and troponin I are unstable proteins with a secondary structure dominated by α-helix, while I-connectin is a stable protein with a secondary structure dominated by random coil. All three proteins are hydrophilic and predicted to be non-toxic on ToxinPreds.