To improve bioremediation of arsenic (As) contamination in soil, the use of microorganisms to efficiently reduce As and their assessment of genetic erosion by DNA damage using genomic template stability (GTS) evaluation and using RAPD markers were investigated. The five sites examined for microorganisms and contaminated soils were collected from affected gold mining areas. The highest As concentration in gold mining soil is 0.72 mg/kg. Microorganism strains isolated from the gold mining soil samples were tested for As removal capacity. Two bacterial isolates were identified by 16S rRNA gene sequence analysis and morphological characteristics as Brevibacillus reuszeri and Rhodococcus sp. The ability to treat As in nutrient agar (NA) at 1,600 mg/L and contaminated soil samples at 0.72 mg/kg was measured at 168 h, revealing more efficient As removal by B. reuszeri than Rhodococcus sp. (96.67% and 94.17%, respectively). Both species have the capacity to remove As, but B. reuszeri shows improved growth compared to the Rhodococcus sp. B. reuszeri might be suitable for adaptation and use in As treatment. The results are in agreement with their genetic erosion values, with B. reuszeri showing very little genetic erosion (12.46%) of culture in As concentrations as high as 1,600 mg/L, whereas 82.54% genetic erosion occurred in the Rhodococcus sp., suggesting that Rhodococcus sp. would not survive at this level of genetic erosion. Therefore, B. reuszeri has a high efficiency and can be used for soil As treatment, as it is capable to tolerate a concentration of 0.72 mg/kg and as high as 1,600 mg/L in NA.