The complete genome sequences of two chemoautotrophic nitrite-oxidizing bacteria of the genus Nitrospina are reported. Nitrospina gracilis strain Nb-211 was isolated from the Atlantic Ocean, and Nitrospina sp. strain Nb-3 was isolated from the Pacific Ocean. We report two highly similar ~3.07-Mbp genome sequences that differ by the presence of ferric iron chelator (siderophore) biosynthesis genes.