In the oceans and seas, environmental conditions change over multiple temporal and spatial scales. Here, we ask what factors affect the bacterial community structure across time, depth and size fraction during six seasonal cruises (2 years) in the ultra-oligotrophic Eastern Mediterranean Sea. The bacterial community varied most between size fractions (free-living (FL) vs. particle-associated), followed by depth and finally season. The FL community was taxonomically richer and more stable than the particle-associated (PA) one, which was characterized by recurrent 'blooms' of heterotrophic bacteria such as Alteromonas and Ralstonia. The heterotrophic FL and PA communities were also correlated with different environmental parameters: the FL population correlated with depth and phytoplankton, whereas PA bacteria were correlated primarily with the time of sampling. A significant part of the variability in community structure could, however, not be explained by the measured parameters. The metabolic potential of the PA community, predicted from 16S rRNA amplicon data using PICRUSt, was enriched in pathways associated with the degradation and utilization of biological macromolecules, as well as plastics, other petroleum products and herbicides. The FL community was enriched in predicted pathways for the metabolism of inositol phosphate, a potential phosphorus source, and of polycyclic aromatic hydrocarbons.