Phenol is a hazardous organic solvent to living organisms, even in its small amounts. In order to bioremediation of phenol from aqueous solution, a novel bacterial strain was isolated from coking wastewater, identified as Rhodococcus qingshengii based on 16S rRNA sequence analysis and named as strain Sahand110. The phenolbiodegrading capabilities of the free and immobilized cells of Sahand110 on the beads of Na-alginate (NA) and magnetic chitosan-alginate (MCA) nanocomposite were evaluated under different initial phenol concentrations (200, 400, 600, 800 and 1000 mg/L). Results illustrated that Sahand110 was able to grow and complete degrade phenol up to 600 mg/L, as the sole carbon and energy source. Immobilized cells of Sahand110 on NA and MCA were more competent than its free cells in degradation of high phenol concentrations, 100% of 1000 mg/L phenol within 96 h, indicating the improved tolerance and performance of the immobilized cells against phenol toxicity. Therefore, the immobilized Sahand110 on the studied beads, especially MCA bead regarding its suitable properties, has significant potential to enhanced bioremediation of phenol-rich wastewaters.