Polycyclic aromatic hydrocarbons (PAHs) are common organic pollutants with great carcinogenic threaten, and metal/PAH-contaminated environments represent one of the most difficult remedial challenges. In this work, Sphingobium yanoikuyae SJTF8 was isolated and identified with great and stable PAH-degrading efficiency even under stress conditions. It could utilize typical PAHs (naphthalene, phenanthrene, and anthracene) and heterocyclic and halogenated aromatic compounds (dibenzothiophene and 9-bromophenanthrene) as the sole carbon source. It could degrade over 98% of 500 mg/L phenanthrene in 4 days, and the cis-3,4-dihydrophenanthrene-3,4-diol was the first-step intermediate. Notably, strain SJTF8 showed great tolerance to heavy metals and acidic pH. Supplements of 0.30 mM of Cu²⁺, 1.15 mM of Zn²⁺, and 0.01 mM of Cd²⁺ had little effect on its cell growth and phenanthrene degradation; phenanthrene of 250 mg/L could still be degraded completely in 48 h. Further, the whole genome sequence of S. yanoikuyae SJTF8 was obtained, and three plasmids were found. The potential genes participating in stress-tolerance and PAH-degradation were annotated and were found mostly distributed in plasmids 1 and 2. Elimination of plasmid 2 resulted in the loss of the PAH-degradation ability. On the basis of genome mining results, the possible degrading pathway and the metabolites of S. yanoikuyae SJTF8 to phenanthrene were predicted.