Modern taxonomy, diagnostics, and forensics of bacteria benefit from technologies that provide data for genome-based classification and identification of strains; however, full genome sequencing is still costly, lengthy, and labor intensive. Therefore, other methods are needed to estimate genomic relatedness among strains in an economical and timely manner. Although DNA-DNA hybridization and techniques based on genome fingerprinting or sequencing selected genes like 16S rDNA, gyrB, or rpoB are frequently used as phylogenetic markers, analyses of complete genome sequences showed that global measures of genome relatedness, such as the average genome conservation of shared genes, can provide better strain resolution and give phylogenies congruent with relatedness revealed by traditional phylogenetic markers. Bacterial genomes are characterized by a high gene density; therefore, we investigated the integration of mass spectrometry-based proteomic techniques with statistical methods for phylogenomic classification of bacterial strains. For this purpose, we used a set of well characterized Bacillus cereus group strains isolated from poisoned food to describe a method that relies on liquid chromatography-electrospray ionization-tandem mass spectrometry of tryptic peptides derived from whole cell digests. Peptides were identified and matched to a prototype database (DB) of reference bacteria with fully sequenced genomes to obtain their phylogenetic profiles. These profiles were processed for predicting genomic similarities with DB bacteria estimated by fractions of shared peptides (FSPs). FSPs served as descriptors for each food isolate and were jointly analyzed using hierarchical cluster analysis methods for revealing relatedness among investigated strains. The results showed that phylogenomic classification of tested food isolates was in consonance with results from established genomic methods, thus validating our findings. In conclusion, the proposed approach could be used as an alternative method for predicting relatedness among microbial genomes of B. cereus group members and potentially may circumvent the need for whole genome sequencing for phylogenomic typing of strains.