Iodide-oxidizing bacteria (IOB), which oxidize iodide (I⁻) to molecular iodine (I₂), were isolated from iodide-rich (63 μM to 1.2 mM) natural gas brine waters collected from several locations. Agar media containing iodide and starch were prepared, and brine waters were spread directly on the media. The IOB, which appeared as purple colonies, were obtained from 28 of the 44 brine waters. The population sizes of IOB in the brines were 10² to 10⁵ colony-forming units (CFU) mL⁻¹. However, IOB were not detected in natural seawaters and terrestrial soils (fewer than 10 CFU mL⁻¹ and 10² CFU g wet weight of soils⁻¹, respectively). Interestingly, after the enrichment with 1 mM iodide, IOB were found in 6 of the 8 seawaters with population sizes of 10³ to 10⁵ CFU mL⁻¹. 16S rDNA sequencing and phylogenetic analyses showed that the IOB strains are divided into two groups within the α-subclass of the Proteobacteria. One of the groups was phylogenetically most closely related to Roseovarius tolerans with sequence similarities between 94% and 98%. The other group was most closely related to Rhodothalassium salexigens, although the sequence similarities were relatively low (89% to 91%). The iodide-oxidizing reaction by IOB was mediated by an extracellular enzyme protein that requires oxygen. Radiotracer experiments showed that IOB produce not only I₂ but also volatile organic iodine, which were identified as diiodomethane (CH₂I₂) and chloroiodomethane (CH₂ClI). These results indicate that at least two types of IOB are distributed in the environment, and that they are preferentially isolated in environments in which iodide levels are very high. It is possible that IOB oxidize iodide in the natural environment, and they could significantly contribute to the biogeochemical cycling of iodine.