Oxygen minimum zones (OMZ) are areas in the global ocean where oxygen concentrations drop to below one percent. Low oxygen concentrations allow alternative respiration with nitrate and nitrite as electron acceptor to become prevalent in these areas, making them main contributors to oceanic nitrogen loss. The contribution of anammox and denitrification to nitrogen loss seems to vary in different OMZs. In the Arabian Sea, both processes were reported. Here, we performed a metagenomics study of the upper and core zone of the Arabian Sea OMZ, to provide a comprehensive overview of the genetic potential for nitrogen and methane cycling. We propose that aerobic ammonium oxidation is carried out by a diverse community of Thaumarchaeota in the upper zone of the OMZ, whereas a low diversity of Scalindua-like anammox bacteria contribute significantly to nitrogen loss in the core zone. Aerobic nitrite oxidation in the OMZ seems to be performed by Nitrospina spp. and a novel lineage of nitrite oxidizing organisms that is present in roughly equal abundance as Nitrospina. Dissimilatory nitrate reduction to ammonia (DNRA) can be carried out by yet unknown microorganisms harbouring a divergent nrfA gene. The metagenomes do not provide conclusive evidence for active methane cycling; however, a low abundance of novel alkane monooxygenase diversity was detected. Taken together, our approach confirmed the genomic potential for an active nitrogen cycle in the Arabian Sea and allowed detection of hitherto overlooked lineages of carbon and nitrogen cycle bacteria.