Two different procedures were compared to isolate polycyclic aromatic hydrocarbon (PAH)-utilizing bacteria from PAH-contaminated soil and sludge samples, i.e., (i) shaken enrichment cultures in liquid mineral medium in which PAHs were supplied as crystals and (ii) a new method in which PAH degraders were enriched on and recovered from hydrophobic membranes containing sorbed PAHs. Both techniques were successful, but selected from the same source different bacterial strains able to grow on PAHs as the sole source of carbon and energy. The liquid enrichment mainly selected for Sphingomonas spp., whereas the membrane method exclusively led to the selection of Mycobacterium spp. Furthermore, in separate membrane enrichment set-ups with different membrane types, three repetitive extragenic palindromic PCR-related Mycobacterium strains were recovered. The new Mycobacterium isolates were strongly hydrophobic and displayed the capacity to adhere strongly to different surfaces. One strain, Mycobacterium sp. LB501T, displayed an unusual combination of high adhesion efficiency and an extremely high negative charge. This strain may represent a new bacterial species as suggested by 16S rRNA gene sequence analysis. These results indicate that the provision of hydrophobic sorbents containing sorbed PAHs in the enrichment procedure discriminated in favor of certain bacterial characteristics. The new isolation method is appropriate to select for adherent PAH-degrading bacteria, which might be useful to biodegrade sorbed PAHs in soils and sludge.