Chemosynthesis increases alkalinity and facilitates stromatolite growth at methane seeps in 731 m water depth within the oxygen minimum zone (OMZ) in the northern Arabian Sea. Microbial fabrics, including mineralized filament bundles resembling the sulfideoxidizing bacterium Thioploca, mineralized extracellular polymeric substances, and fossilized rod-shaped and filamentous cells, all preserved in 13C-depleted authigenic carbonate, suggest that biofilm calcification resulted from nitrate-driven sulfide oxidation (ND-SO) and sulfate-driven anaerobic oxidation of methane (SD-AOM). Geochemical batch modeling reveals that the collective effects of ND-SO and SD-AOM increase alkalinity more than SD-AOM alone, explaining the preservation of sulfide-oxidizing bacteria in authigenic carbonate. These findings demonstrate the biogenicity of a conical stromatolite associated with OMZ methane seeps and confirm the fact that, apart from photosynthesis-based metabolisms, chemosynthesis-based metabolisms can also account for stromatolite formation.