In this work, we demonstrate that the rhizosphere of common duckweed (Lemna minor) is inhabited with various phenol-resistant bacterial strains. Based on 16S rRNA sequencing, we have identified 60 rhizosphere-associated bacterial isolates belonging to 10 different bacterial genera (Pseudomonas, Hafnia, Serratia, Enterobacter, Micrococcus, Stenotrophomonas, Xanthomonas, Bacillus, Staphylococcus and Klebsiella). All isolates have been tested for phenol resistance and ability to utilize phenol as the sole carbon source. 70% of all isolates survived high doses of phenol (≥200 mg/L) and at least 27% can be potentially acclimatized by gradual increase of phenol concentration. Finally, based on high phenol resistance, ability to utilize phenol as the sole carbon source and documented low pathogenicity, we propose 5 strains as potentially excellent candidates for bioremediation. These 5 strains taxonomically correspond to Klebsiella sp., Serratia sp., and Hafnia sp., respectively. To the best of our knowledge, this is the first attempt to assess decontamination capacity of Serratia nematodiphila and Hafnia sp. in the context of bioremediation of phenol-contaminated aqueous media. Although additional analyses are needed, interaction between the common duckweed and the selected bacterial strains may be utilized in future bioremediation strategies.