With the increased usage of nitrate fertilizers, as it is a stable ion with high solubility in water, its removal is a challenge for human health. Several physicochemical methods have been examined for nitrate removal of water, but nowadays the biological treatment of it from soil and water are widely used because of its high efficiency and low cost. To remove nitrogen from such environments, we studied nitrate reducing halophilic and halotolerant bacteria. A total of 50 strains of halophilic and halotolerant bacteria from different saline and hypersaline environments of Iran, including Incheboron wetland, Aran-Bidgol Lake and Urmia Lake, were screened for nitrate reductase production. Among isolated bacteria, 60% of strains isolated from Urmia Lake and 19% of strains isolated from Incheboron wetland produced nitrate reductase. Nitrate reductase coding genes narG and napA were analyzed for all the nitrate reducing strains. The napA gene was amplified successfully from a gram negative halophilic strain and narG gene was detected in ten halophilic strains. Among nitrate reducing isolates, Kocuria rosea strain R3A34 which has narG gene showed the most nitrate reductase production. The strain R3A34 was selected for optimization of denitrifying activity. Statistical results have shown that the optimum conditions for the production of nitrate reductase were 32 °C, pH 7.0, NaCl 8 % (w/v) and mannitol as carbon source. Furthermore, as these conditions are common in wastewaters, this bacterium can be a proper candidate for bioremediation of wastewaters from nitrate pollutants.