The proteasome is a multisubunit structure that degrades proteins. Protein degradation is an essential component of regulation because proteins can become misfolded, damaged, or unnecessary. Proteasomes and their homologues vary greatly in complexity: from HslV (heat shock locus v), which is encoded by 1 gene in bacteria, to the eukaryotic 20S proteasome, which is encoded by more than 14 genes. Despite this variation in complexity, all the proteasomes are composed of homologous subunits. We searched 238 complete bacterial genomes for structures related to the proteasome and found evidence of two novel groups of bacterial proteasomes. The first, which we name Anbu, is sparsely distributed among cyanobacteria and proteobacteria. We hypothesize that Anbu must be very ancient because of its distribution within the cyanobacteria, and that it has been lost in many more recent species. We also present evidence for a fourth type of bacterial proteasome found in a few β-proteobacteria, which we call β-proteobacteria proteasome homologue (BPH). Sequence and structural analyses show that Anbu and BPH are both distinct from known bacterial proteasomes but have homologous structures. Anbu is encoded by one gene, so we postulate a duplication of Anbu created the 20S proteasome. Anbu’s function appears to be related to transglutaminase activity, not the general stress response associated with HslV. We have found different combinations of Anbu, BPH, and HslV within these bacterial genomes, which raises questions about specialized protein degradation systems.