The Gram-negative bacterium Paenalcaligenes niemegkensis NGK35T was isolated from plastic debris in an abandoned landfill. It has the ability to grow on polyethylene and hexadecane as the sole carbon sources. Here, we report the corresponding draft genome, which contains 3.66 Mbp and is characterized by a G+C content of 52.1%.