Half of the microbial cells in the Earth’s oceans are found in sediments1. Many of these cells are members of the Archaea2, single-celled prokaryotes in a domain of life separate from Bacteria and Eukaryota. However, most of these archaea lack cultured representatives, leaving their physiologies and placement on the tree of life uncertain. Here we show that the uncultured miscellaneous crenarchaeotal group (MCG) and marine benthic group-D (MBG-D) are among the most numerous archaea in the marine sub-sea floor. Single-cell genomic sequencing of one cell of MCG and three cells of MBG-D indicated that they form new branches basal to the archaeal phyla Thaumarchaeota3 and Aigarchaeota4, for MCG, and the order Thermoplasmatales, for MBG-D. All four cells encoded extracellular protein-degrading enzymes such as gingipain and clostripain that are known to be effective in environments chemically similar to marine sediments. Furthermore, we found these two types of peptidase to be abundant and active in marine sediments, indicating that uncultured archaea may have a previously undiscovered role in protein remineralization in anoxic marine sediments.