Knowledge of Earth’s microbiomes’ capacity to degrade aromatic compounds is limited by the lack of accurate tools for identifying degrading genes and their associated taxa. Additionally, these estimates are hardly compared to in situ background concentrations of polycyclic aromatic hydrocarbons (PAHs), particularly in oceanic waters. This knowledge is important for assessing the persistence of the widespread and abundant PAHs in the environment and their interactions with microbes. Here, we present a new tool to identify aromatic ring-hydroxylating dioxygenase α-subunit (arhdA) gene sequences by combining profile-based search with phylogenetic placement in a reference phylogeny. We identified arhdA-harboring taxa in both the Genome Taxonomy Database and the Malaspina Vertical Profiles Gene Database, a gene catalog derived from metagenomes collected during the Malaspina expedition. We found that multiple ubiquitous taxa in tropical and temperate oceans harbor arhdA. The comparison of arhdA gene abundances in seawater metagenomes with the field PAH concentrations showed that higher abundances of arhdA gene copies per cell were negatively correlated with 2–4 ring PAHs, consistent with the known degradation of lighter PAHs. Gene abundances were significantly higher in the particle-associated fraction than in the free-living fraction, suggesting particulate matter as a relevant reservoir of PAH degraders. Finally, we show that PAHs, together with other environmental variables, modulate the structure of oceanic microbial communities.