Strain 113P3 was isolated from activated sludge and identified as a polyvinyl alcohol (PVA)-degrading Pseudomonas species; it was later reidentified as Sphingopyxis species. Only three genes are directly relevant to the metabolism of PVA and comprise the pva operon, which was deposited as accession no. AB190228. Here, we report the complete genome sequence of strain 113P3, which has been conserved as a stock culture (NBRC 111507) at the Biological Resource Center, National Institute of Technology and Evaluation (NITE) (Tokyo, Japan). The genome of strain 113P3 is composed of a 4.4-Mb circular chromosome and a 243-kb plasmid. The whole finishing was conducted in silico except for four PCRs. The sequence corresponding to AB190288 exists on the chromosome.