We report the genome sequence of a polyethylene-degrading bacterial strain identified as Stenotrophomonas maltophilia strain PE591, which was isolated from plastic debris found in savanna soil. The genome was assembled in 16 scaffolds with a length of 4,751,236 bp, a GC content of 66.5%, and 4,432 predicted genes.