Among the 49 strains of moderately halophilic bacteria isolated from the salty environments of Iran, a Gram-positive coccus designated as strain QW6 showed high capacity in the removal of toxic oxyanions of tellurium in a wide range of culture medium factors including pH (5.5–10.5), temperature (25–45 °C), various salts including NaCl, KCl, and Na2SO4 (0.5–4 M), selenooxyanions (2–10 mM), and at different concentrations of potassium tellurite (0.5–1mM) under aerobic condition. Phenotypic characterization and phylogenetic analyses based on 16S rDNA sequence comparisons indicated that this strain was a member of the genus Salinicoccus. The maximum tellurite removal was exhibited in 1.5 M NaCl at 35 °C, while the activity reduced by 53% and 47% at 25 and 45 °C, respectively. The optimum pH for removal activity was shown to be 7.5, with 90% and 83% reduced removal capacities at the two extreme values of 5.5 and 10, respectively. The impact of different concentrations of selenooxyanions (2–10 mM) on tellurite removal by strain QW6 was evaluated. The ability of strain QW6 in the removal of tellurite in the presence of 6 mM selenite increased by 25%. The concentration of toxic potassium tellurite in the supernatant of the bacterial culture medium decreased by 99% (from 0.5 to 0.005 mM) after 6 days and the color of the medium changed to black due to the formation of less toxic elemental tellurium