As a step toward bioaugmentation of coking wastewater treatment 45 bacteria strains were isolated from the activated sludge of a coking wastewater treatment plant (WWTP). Three strains identified as Bacillus cereus, Pseudomonas synxantha, and Pseudomonas pseudoaligenes exhibited high dehydrogenase activity which indicates a strong ability to degrade organic matter. Subsequently all three strains showed high naphthalene degradation abilities. Naphthalene is a refractory compound often found in coking wastewater. For B. cereus and P. synxantha the maximum naphthalene removal rates were 60.4% and 79.8%, respectively, at an initial naphthalene concentration of 80 mg/L, temperature of 30 °C, pH of 7, a bacteria concentration of 15% (V/V), and shaking speed of 160 r/min. For P. pseudoaligenes, the maximum naphthalene removal rate was 77.4% under similar conditions but at 35 °C.