Anammox bacteria perform anaerobic ammonium oxidation (anammox) and have a unique compartmentalized cell consisting of three membrane-bound compartments (from inside outwards): the anammoxosome, riboplasm, and paryphoplasm. The cell envelope of anammox bacteria has been proposed to deviate from typical bacterial cell envelopes by lacking both peptidoglycan and a typical outer membrane. However, the composition of the anammox cell envelope is presently unknown. Here, we investigated the outermost layer of the anammox cell and identified a proteinaceous surface layer (S-layer) (a crystalline array of protein subunits) as the outermost component of the cell envelope of the anammox bacterium “Candidatus Kuenenia stuttgartiensis.” This is the first description of an S-layer in the phylum of the Planctomycetes and a new addition to the cell plan of anammox bacteria. This S-layer showed hexagonal symmetry with a unit cell consisting of six protein subunits. The enrichment of the S-layer from the cell led to a 160-kDa candidate protein, Kustd1514, which has no homology to any known protein. This protein is present in a glycosylated form. Antibodies were generated against the glycoprotein and used for immunogold localization. The antiserum localized Kustd1514 to the S-layer and thus verified that this protein forms the “Ca. Kuenenia stuttgartiensis” S-layer.