The mangrove ecosystem is a marginal and complex ecosystem. Mangrove trees can tolerate heat, desiccation, high salinity, radiation, and anoxic conditions. The physiological features of mangroves help them tolerate these stressors, but their relationship with prokaryotic communities also plays a role in a productive mangrove ecosystem, mainly in nutrient cycling and biogeochemical transformation. In Saudi Arabia, a few studies were conducted to understand the microbial communities residing in the mangrove ecosystem. Most of the studies were focused on the sediments or rhizosphere of the most dominant species in the kingdom, Avicennia marina. In this study, the bacterial composition of two mangrove species (Avicennia marina and Rhizophora mucronata) and the relationship between them was explored using next generation amplicon sequencing of the V3-V4 region of the 16S rRNA. In both species, samples from four compartments were collected (sediments, rhizosphere, roots, and leaves). Both species had a similar microbial composition, with Proteobacteria and Chloroflexi being the most dominant phyla in all compartments. The lack of difference in alpha diversity measures (number of ASVs and Shannon-diversity index) between species highlights the symbiotic relationship between the trees. Previous studies have reported that A. marina has a more diverse microbial community than R. mucronata, however this difference was not significant in our samples. The multivariate analysis showed us that the microbial composition of the leaf and root samples was grouped separately from the microbial composition of sediment and rhizosphere samples, highlighting the specific microbial composition of each compartment. In addition, the enriched strains in each cluster were explored and related to the surrounding environment of the mangrove ecosystem, followed by the exploration of unique strains in each compartment using SIMPER analysis. In conclusion, this study provides the first information on the Red Sea Northern mangrove (Al-Wajh region) tree microbiomes, encompassing roots, leaves, rhizosphere, and sediments. Furthermore, by showing that some bacteria can colonize different plant compartments we contribute to disentangling their propagation channels within plants.