We report the draft genome sequence of 3.3 Mb and the sequence (19.2 kb) of a natural plasmid isolated from Phenylobacterium immobile strain E (DSM 1986), able to degrade xenobiotic compounds as the sole carbon source. The sequences reveal a large number of novel Rieske nonheme iron aromatic ring-hydroxylating oxygenases (RHOs).