Alicycliphilus denitrificans strain BC and A. denitrificans strain K601(T) degrade cyclic hydrocarbons. These strains have been isolated from a mixture of wastewater treatment plant material and benzene-polluted soil and from a wastewater treatment plant, respectively, suggesting their role in bioremediation of soil and water. Although the strains are phylogenetically closely related, there are some clear physiological differences. The hydrocarbon cyclohexanol, for example, can be degraded by strain K601(T) but not by strain BC. Furthermore, both strains can use nitrate and oxygen as an electron acceptor, but only strain BC can use chlorate as electron acceptor. To better understand the nitrate and chlorate reduction mechanisms coupled to the oxidation of cyclic compounds, the genomes of A. denitrificans strains BC and K601(T) were sequenced. Here, we report the complete genome sequences of A. denitrificans strains BC and K601(T).