Recently, there have been advances in the genome analysis of numerous living organisms, including humans. In one post-genome study, the term “proteomics” has attracted much attention. Although proteomics have been widely investigated in the medical and pharmaceutical fields, only a few proteomic studies in the field of food sciences have been reported. Therefore, in this study, proteomic techniques were applied to an analysis of quality evaluations of fish during storage. Specifically, detailed changes in fish proteins during storage were analyzed using two-dimensional electrophoresis and mass spectrometry. We investigated the early oxidative proteins of bonito muscle during storage, and several proteins were identified by homology search using the NCBI genome database. Thus, the proteomic technique is available to the field of food science.