Anaerobic ammonium oxidization (anammox) has been widely recognized for its importance in global nitrogen cycle. While, their distributions in the Eastern Indian Ocean (EIO) still remain unknown. This study investigated the diversity and abundance of anammox bacteria from water column (0–2000 m with seven depths) down to the surface sediments in the EIO targeting 16S rRNA gene by using clone library and quantitative real-time PCR (qPCR) analysis. Results showed a wide distribution of anammox bacteria in both water column and sediments in the EIO, with the Candidatus Scalindua sp. assemblage as the predominant group among the anammox communities. The diversity of anammox bacteria was higher in water column, but abundances (based on copy numbers of 16S rRNA gene) were lower than the corresponding sediment samples. Non-metric multidimensional scaling analysis demonstrated distinct spatial patterns (both horizontal and vertical): samples from the Bay of Bengal and the Equator showed strong stratification in different layers and were distinct from other two regions. Canonical correspondence analysis indicated that dissolved oxygen, temperature, and nitrate were the major environmental factors shaping the distribution of anammox bacteria. This is the first investigation on detailed community structure and distribution of anammox bacteria in the EIO, and the results are consistent with (i) potential contribution of sedimentary anammox bacteria towards nitrogen removal, and (ii) dispersal of anammox bacteria diversity via the ocean.