The Baltic Sea is a unique brackish water ecosystem that has been studied for decades; however, knowledge about the diversity of the benthic communities of bacteria and microbial eukaryotes within this system is sparse. Using an amplicon sequencing approach, we evaluated alpha and beta diversity of shallow-water coastal microbial sediment communities and their relationship to several environmental factors, on both a large spatial scale in the Baltic Sea and the adjacent North Sea, as well as on a temporal scale at selected sites along the salinity gradient in the Baltic Sea. We found salinity to be among the drivers of alpha diversity for bacteria but not for eukaryotes; however, community network structure appeared to change between sites of different salinity. Furthermore, beta diversity analyses revealed that communities in the poly- to mesohaline sections of the study area were affected to a higher degree by temperature, nutrient and sediment characteristics. This study shows that the structure of coastal microbial communities is to some degree related to salinity, but other factors also play a role.