Paenibacillus sp. strain A9 is an important bioflocculant-producing bacterium, isolated from a soil sample, and is pale pink-pigmented, aerobic, and Gram-positive. Here, we report the draft genome sequence and the initial findings from a preliminary analysis of strain A9, which is a novel species of Paenibacillus.