Provenance and traceability are crucial aspects of seafood safety, supporting managers and regulators, and allowing consumers to have clear information about the origin of the seafood products they consume. In the present study, we developed an innovative spectral approach based on total reflection X-ray fluorescence (TXRF) spectroscopy to identify the provenance of seafood and present a case study for five economically relevant marine species harvested in different areas of the Atlantic Portuguese coast: three bony fish—Merluccius merluccius, Scomber colias, and Sparus aurata; one elasmobranch—Raja clavata; one cephalopod—Octopus vulgaris. Applying a first-order Savitzky–Golay transformation to the TXRF spectra reduced the potential matrix physical effects on the light scattering of the X-ray beam while maintaining the spectral differences inherent to the chemical composition of the samples. Furthermore, a variable importance in projection partial least-squares discriminant analysis (VIP-PLS-DA), with k − 1 components (where k is the number of geographical origins of each seafood species), produced robust high-quality models of classification of samples according to their geographical origin, with several clusters well-evidenced in the dispersion plots of all species. Four of the five species displayed models with an overall classification above 80.0%, whereas the lowest classification accuracy for S. aurata was 74.2%. Notably, about 10% of the spectral features that significantly contribute to class differentiation are shared among all species. The results obtained suggest that TXRF spectra can be used for traceability purposes in seafood species (from bony and cartilaginous fishes to cephalopods) and that the presented chemometric approach has an added value for coupling with classic TXRF spectral peak deconvolution and elemental quantification, allowing characterization of the geographical origin of samples, providing a highly accurate and informative dataset in terms of food safety.