Many prokaryotes encode protein-based encapsulin nanocompartments, including anaerobic ammonium oxidizing (anammox) bacteria. This study expands the list of known anammox encapsulin systems from freshwater species to include the marine genus Scalindua. Two novel systems, identified in "Candidatus Scalindua rubra" and "Candidatus Scalindua sp. SCAELEC01 167" possess different architectures than previously studied freshwater anammox encapsulins. Characterization of the S. rubra encapsulin confirms that it can self-assemble to form compartments when heterologously expressed in Escherichia coli. BLASTp and HMMER searches of additional genomes and metagenomes spanning a range of environments returned 26 additional novel encapsulins, including a freshwater anammox encapsulin identified in "Candidatus Brocadia caroliniensis". Phylogenetic analysis comparing these 28 new encapsulin sequences and cargo to that of their closest known relatives shows that encapsulins cluster by cargo protein type and therefore likely evolved together. Lastly, prokaryotic encapsulins may be more common and diverse than previously thought. Through searching a small sample size of all public metagenomes and genomes, many new encapsulin systems were unearthed by this study. This suggests that many additional encapsulins likely remain to be discovered.