The Martian regolith is known to contain a maximum of 0.5% (w/v) perchlorate (ClO4−) that is toxic for most living organisms. With such high concentrations of perchlorates on Mars, is there any possibility of life? Here, in order to search and identify potential organisms on Earth, which could survive the perchlorate levels on Mars, we have isolated four perchlorate resistant, halophilic/halotolerant bacterial species from Big Soda Lake (BSL) in Nevada, USA. The 16S ribosomal RNA sequences revealed that these halophiles belong to the genera Bacillus, Alkalibacillus and Halomonas. Growth curves were obtained using a saline medium with different concentrations of magnesium, sodium and/or calcium perchlorate salt to simulate the Martian eutectic brine water. All four species, BSL1-4, grew in high saline media in the presence of perchlorates. This is the first growth experiment using multiple perchlorate salts. BSL3 relative to Halomonas salifodinae showed high maximum growth (Optical Density) comparing with other isolates in the presence of 1% perchlorate salts. Also, BSL1 relative to Bacillus licheniformis survived in the presence of 5% Na-perchlorate, but growth was slower in the absence of Na-perchlorate. The results revealed that these new model microbes are capable of tolerating the hypothesized hypersaline and perchlorate-rich Martian subsurface water environment. Perchlorate-resistant halophile would serve as a new model to understand the biochemistry that may occur on Mars.