Bioremediation of soils contaminated with wood preservatives containing polycyclic aromatic hydrocarbons (PAHs) is desired because of their toxic, mutagenic, and carcinogenic properties. Creosote wood preservative–contaminated soils at the Champion International Superfund Site in Libby, Montana currently undergo bioremediation in a prepared-bed land treatment unit (LTU) process. Microbes isolated from these LTU soils rapidly mineralized the 14C-labeled PAH pyrene in the LTU soil. Gram staining, electron microscopy, and 16S rDNA-sequencing revealed that three of these bacteria, JLS, KMS, and MCS, were Mycobacterium strains. The phylogeny of the 16S rDNA showed that they were distinct from other Mycobacterium isolates with PAH-degrading activities. Catalase and superoxide dismutase (SOD) isozyme profiles confirmed that each isolate was distinct from each other and from the PAH-degrading mycobacterium, Mycobacterium vanbaalenii sp. nov, isolated from a petroleum-contaminated soil. We find that dioxygenase genes nidA and nidB are present in each of the Libby Mycobacterium isolates and are adjacent to each other in the sequence nidB-nidA, an order that is unique to the PAH-degrading mycobacteria.