Aeolian prokaryotic communities (APC) are important components of bioaerosols that are transported freely or attached to dust particles suspended in the atmosphere. Terrestrial and marine ecosystems are known to release and receive significant prokaryote loads into and from the surrounded atmospheric air. However, compared to terrestrial systems, there is a lack of microbial characterization of atmospheric dust over marine systems, such as the Red Sea, which receives significant terrestrial dust loads and is centrally located within the Global Dust Belt. Prokaryotic communities are likely to be particularly important in the Global Dust Belt, the area between the west coast of North Africa and Central Asia that supports the highest dust fluxes on the planet. Here we characterize the diversity and richness of the APC over the Red Sea ecosystem, the only sea fully contained within the Global Dust Belt. MiSeq sequencing was used to target 16S ribosomal DNA of two hundred and forty aeolian dust samples. These samples were collected at ∼7.5 m high above the sea level at coastal and offshore sampling sites over a 2-year period (2015–2017). The sequencing outcomes revealed that the APC in the atmospheric dust is dominated by Proteobacteria (42.69%), Firmicutes (41.11%), Actinobacteria, (7.69%), and Bacteroidetes (3.49%). The dust-associated prokaryotes were transported from different geographical sources and found to be more diverse than prokaryotic communities of the Red Sea surface water. Marine and soil originated prokaryotes were detected in APC. Hence, depending on the season, these groups may have traveled from other distant sources during storm events in the Red Sea region, where the APC structure is influenced by the origin and the concentration of aeolian dust particles. Accordingly, further studies of the impact of atmospheric organic aerosols on the recipient environments are required.