The structure characteristics and biosorption behaviors of heavy metals on a novel exopolysaccharide, which was secreted by the thermophilic Anoxybacillus sp. R4-33 isolated from a radon hot spring in China, were investigated. We purified the EPS-II from the culture medium of strain Anoxybacillus sp. R4-33 using a DEAE Sepharose and Sephadex G-200 column. The results of partial acid hydrolysis, gas chromatography, infrared spectrum, and nuclear magnetic resonance analysis showed that EPS-II was a heteropolysaccharide, composed of d-mannose and d-glucose as its principal monosaccharide composition in the relative proportions 1:0.45. Batch adsorption processes were conducted to characterize the kinetics, equilibrium, and mechanisms of the biosorption process of Zn(II) and Cd(II) from aqueous solution. Sorption experiments confirmed that 1.9783 mg Zn(II) and 1.4095 mg Cd(II) were adsorbed per gram EPS-II at pH 6.0, respectively. The equilibrium data was described by two isotherm models (Langmuir and Freundlich) and two kinetics models (pseudo-first order and pseudo-second order). Freundlich model provided the better correlation of Zn(II) biosorption data, while Langmuir model did to Cd(II). Pseudo-second-order kinetic equation could depict the biosorption kinetics of tested heavy metals. The EPS-II would be a potential candidate in the exopolysaccharide bioresource.