The soil and groundwater of the Bhagobangola I block of Murshidabad district, West Bengal, India is severely arsenic-contaminated. A bacterium was isolated from the garden soil of the Mahishasthali village, which could tolerate 36.49 mM arsenic (III), 280.44 mM arsenic (V) and 63 mM chromium (III), which makes it arsenic (III and V) and chromium (III) hyper-tolerant bacterium. The growth pattern of this bacterium does not show much alteration in the presence of 10 mM arsenic (III) and chromium (III), emphasizing its resistance to these heavy metals. Scanning electron microscopic analysis depicted this bacterium to be rod-shaped with a size of ~1.45 µm. 16S rDNA sequencing, followed by subsequent phylogenetic analysis, established the identity of this bacterium as Microbacterium paraoxydans. This bacterium is capable of bioremediation of arsenic and showed 30.8% and 35.2% of bioremediation for 1mM and 22.6%, and 30.5% of bioremediation for 4mM arsenite, over a period of 24 and 48 h, respectively. Microbacterium paraoxydans also exhibits potential plant growth-promoting properties such as nitrogen fixation, phosphate solubilization, indole-3-acetic acid production and production of siderophores. Therefore, the heavy metal resistance, bioremediation potential and plant growth-promoting potential of the bacterium could be utilized not only for reduction in arsenic toxicity in soil and groundwater but also for plant growth promotion.