Bacteriocins are ribosomally-synthesized peptides or proteins produced by a wide range of bacteria. The antimicrobial activity of this group of natural substances against foodborne pathogenic and spoilage bacteria has raised considerable interest for their application in food preservation. Classifying these bacteriocins in well defined classes according to their biochemical properties is a major step towards characterizing these anti-infective peptides and understanding their mode of action. Actually, the chosen criteria for bacteriocins' classification lack consistency and coherence. So, various classification schemes of bacteriocins resulted various levels of contradiction and sorting inefficiencies leading to bacteriocins belonging to more than one class at the same time and to a general lack of classification of many bacteriocins. Establishing a coherent and adequate classification scheme for these bacteriocins is sought after by several researchers in the field. It is not straightforward to formulate an efficient classification scheme that encompasses all of the existing bacteriocins. In the light of the structural data, here we revisit the previously proposed contradictory classification and we define new structure-based sequence fingerprints that support a subdivision of the bacteriocins into 12 groups. The paper lays down a resourceful and consistent classification approach that resulted in classifying more than 70% of bacteriocins known to date and with potential to identify distinct classes for the remaining unclassified bacteriocins. Identified groups are characterized by the presence of highly conserved short amino acid motifs. Furthermore, unclassified bacteriocins are expected to form an identified group when there will be sufficient sequences.