Low levels of phenol and m-cresol were effectively removed from wastewater under anoxic condition using immobilized sludge. A 138-day experiment was conducted using wastewater containing NO3-N (22.3 mg·1−1), phenol (10 mg·1−1) and m-cresol (5 mg·1−1) at 30°C using sucrose (50 mg·1−1) as co-substrate in an upflow reactor packed with polyvinyl alcohol (PVA) beads entrapped with anoxic sludge and powdered activated carbon (PAC). Throughout the experiment, phenol and m-cresol in the effluent were below the detectable level of 1.0 mg·1−1 even when HRT (hydraulic retention time) was as low as 0.55 hour. The effluent quality in general decreased with HRT. At 5.9 hours of HRT, the reactor effluent contained 5.9 mg·1−1 of COD (chemical oxygen demand) and 1.3 mg·1−1 of NO3-N; but at 0.55 hour, they were, 17.3 and 5.7 mg·1−1, respectively. The effluent COD was from the unidentified soluble microbial products. Methane was not produced after the startup, and all PVA beads were not disintegrated. Results of a batch test showed that organic substrate was preferably consumed by the denitrify bacteria in favor of methane-producing bacteria. Scanning electron micrographs showed that most bacteria were populated on the bead surface due to the availability of nitrate and substrate.