This work examines the role of mycelia in enhancing the degradation by attached bacteria of organic pollutants that have poor bioavailability. Two oomycetes, Pythium oligandrum and Pythium aphanidermatum, were selected as producers of mycelial networks, while Mycobacterium gilvum VM552 served as a model polycyclic aromatic hydrocarbon (PAH) degrading bacterium. The experiments consisted of bacterial cultures exposed to a nondisturbed nonaqueous phase liquid (NAPL) layer containing a heavy fuel spiked with 14C-labeled phenanthrene that were incubated in the presence or absence of the mycelia of the oomycetes in both shaking and static conditions. At the end of the incubation, the changes in the total alkane and PAH contents in the NAPL residue were quantified. The results revealed that with shaking and the absence of mycelia, the strain VM552 grew by utilizing the bulk of alkanes and PAHs in the fuel; however, biofilm formation was incipient and phenanthrene was mineralized following zero-order kinetics, due to bioavailability limitations. The addition of mycelia favored biofilm formation and dramatically enhanced the mineralization of phenanthrene, up to 30 times greater than the rate without mycelia, possibly by providing a physical support to bacterial colonization and by supplying nutrients at the NAPL/water interface. The results in the static condition were very different because the bacterial strain alone degraded phenanthrene with sigmoidal kinetics but could not degrade alkanes or the bulk of PAHs. We suggest that bacteria/oomycete interactions should be considered not only in the design of new inoculants in bioremediation but also in biodegradation assessments of chemicals present in natural environments.