Recent reports suggest that Mycobacterium is better adapted to soils containing poorly bioavailable polycyclic aromatic hydrocarbons (PAHs) compared to Sphingomonas. To study this hypothesis, artificial conditions regarding PAH profile and PAH bioavailability were induced in two PAH-contaminated soils and the response of the eubacterial, Mycobacterium, and Sphingomonas communities to these changed conditions was monitored during laboratory incubation. Soil K3663 with a relatively high proportion of high molecular weight PAHs was amended with phenanthrene or pyrene to artificially change the soil into a soil with a relatively increased bioavailable PAH contamination. Soil AndE with a relatively high proportion of bioavailable low molecular weight PAHs was treated by a single-step Tenax extraction to remove the largest part of the easily bioavailable PAH contamination. In soil K3663, the added phenanthrene or pyrene compounds were rapidly degraded, concomitant with a significant increase in the number of phenanthrene and pyrene degraders, and minor and no changes in the Mycobacterium community and Sphingomonas community, respectively. However, a transient change in the eubacterial community related to the proliferation of several gamma-proteobacteria was noted in the phenanthrene-amended soil. In the extracted AndE soil, the Sphingomonas community initially developed into a more diverse community but finally decreased in size below the detection limit. Mycobacterium in that soil never increased to a detectable size, while the eubacterial community became dominated by a gamma-proteobacterial population. The results suggest that the relative bioavailability of PAH contamination in soil affects bacterial community structure but that the behavior of Mycobacterium and Sphingomonas in soil is more complex than prospected from studies on their ecology and physiology.