Perchlorate is a toxicant when discharged into the environment creates serious implications on human beings. In order to carry out perchlorate remediation, microbial screening has been carried out for the identification of perchlorate degrading isolates from enriched culture media. Two strains were isolated and named ARJR SMBS and LMN SMBS. These are the first perchlorate respiring bacteria (PRBs) which come under Gamma Proteobacteria outside of the phylogenetic groupings of known PRBs. The secondary structure of the bacterial 16S rDNA and restriction site analysis was predicted using Genbee and NEB cutter software. The results show that strain ARJR SMBS contains GC: AT in the ratio of 55:45 with free energy of structure -338.9 kkal/mol whereas the strain LMN SMBS contains GC: AT in the ratio of 54:46 with free energy of structure -323.5 kkal/mol. Phylogenetic tree analyses of 16s rRNA gene sequences revealed that strain ARJR SMBS belongs to the class of gamma Proteobacteria and strain LMN SMBS belongs to pseudomonas species. Growth curve and perchlorate degradation efficiency were studied and strain ARJR SMBS was found to have better degradation efficiency compared to strain LMN SMBS. This study can be summarized as mild growth inhibitory effect of perchlorate with potential perchlorate degrading isolates ARJR SMBS and LMN SMBS. Probably in future, strain ARJR SMBS would be relevant for the design of perchlorate remediation systems.