Authentication of food is a major concern worldwide to ensure that food products are correctly labeled in terms of which animals are actually processed for consumption. Normally authentication is based on species recognition by comparison of selected sequences of DNA or protein. We here present a new robust, proteome-wide tandem mass spectrometry method for species recognition and food product authentication. The method does not use or require any genome sequences or selection of tandem mass spectra but uses all acquired data. The experimental steps were performed in a simple, standardized workflow including protein extraction, digestion, and data analysis. First, a set of reference spectral libraries was generated using unprocessed muscle tissue from 22 different fish species. Query tandem mass spectrometry data sets from "unknown" fresh muscle tissue samples were then searched against the reference libraries. The number of matching spectra could unambiguously identify the origin of all fresh samples. A number of processed samples were also analyzed to further test the robustness and applicability of the method. The results clearly show that the method is also able to correctly identify heavily processed samples.