We developed a novel single-stage autotrophic nitrogen-removal process comprised of two composite immobilized biomass layers—one of nitrifying bacteria and one of sulfur-denitrifying bacteria and elemental sulfur—in a Fe-Ni fibrous slag matrix. Nitrification and consumption of dissolved oxygen occurred in the outer part and sulfur denitrification in the anoxic inner part of the composite matrix, thus realizing autotrophic nitrogen removal in a single reactor. The complete conversion of ammonia into N2 in a single reactor was demonstrated in both batch-mode incubation and continuous-feed operation. The spatial profiles of the ammonia-oxidizing bacteria and denitrifying bacteria were evaluated by real-time PCR, targeting their functional genes, and stratification of these two types was observed in the matrix after several months of incubation. This process does not require any specific reactor type or conditions and thus has the potential to be applied to many different wastewater treatment processes due to its simplicity in both operation and construction.