Structural changes in plankton primary producers have large implications for food web dynamics, energy fluxes and the vertical export of biogenic particulate carbon. Here we examine phytoplankton data spanning the period 1993–2008 from the Bay of Tunis, southwestern Mediterranean Sea, in relation to long term hydroclimate variability. We show a conspicuous shift in the structure of the phytoplankton community characterized by an increase of small-sized species and diversity loss, revealing a dominance of smaller blooming diatoms and cyanobacteria. Such changes were concurrent with marked modifications in hydroclimatic patterns experienced in the Bay of Tunis consisting of a shift towards enhanced winter precipitation together with rising temperatures. This novel study shows an overall rise in the proportion of small phytoplankton cells and a decreasing trend in phytoplankton diversity in the southern Mediterranean area. These findings warn of a potential decline of trophic efficiency and lesser food web stability resulting from mean size reduction and the diversity loss.