In this study, we investigated the in situ responses of Red Sea picophytoplankton, the dominant phytoplankton group in the oligotrophic ocean, to two toxic polycyclic aromatic hydrocarbons (PAHs), phenanthrene and pyrene. The experiments were conducted across a latitudinal gradient of the Saudi Arabian Red Sea, an area sensitive to oil pollution. We observed significant adverse effects on the growth and abundance of the picocyanobacteria Synechococcus and picoeukaryotes, at all stations sampled. Prochlorococcus, which was abundant only at one of the stations, also appeared to be affected. Pyrene was found to be more toxic to phytoplankton at all stations. In general, picoeukaryotes exhibited higher sensitivity to PAHs than Synechococcus. Populations in the highly oligotrophic Northern region of the Red Sea were more tolerant to PAHs, presumably influenced by the natural selection of more resistant strains of phytoplankton due to the prolonged exposure to PAHs. Toxicity threshold values estimated here are higher than those reported for picophytoplankton from other oligotrophic marine waters and exceed by far the natural levels of PAHs in many oceans. Our findings reveal a possible adaptation of picophytoplankton populations to oil-related contaminants, which may clearly influence their spatial distribution patterns in the Red Sea.