The wide anthropogenic use of selenium compounds represents the major source of selenium pollution worldwide causing environmental problems and health concerns. The current study aimed at isolating sixteen bacterial strains, capable of transforming toxic SeO32- to non-toxic elemental selenium, from sediment, water, and mangrove leaves in two mangrove study areas (17 km south of Safaga and 35 km north of Quseir). Geospatial technology was used to detect the location of the mangrove areas. Microbes were isolated using membrane filter technique and direct bacterial plating on salt peptone (SP) agar supplemented with 5mM sodium selenite. Morphological, biochemical, Scanning Electron Microscope (SEM), and Transmission Electron Microscope (TEM) analysis of two bacterial isolates were identified using 16S rRNA gene sequencing. Results showed that the red colonies of sixteen isolates signify the reduction of selenite to red elemental selenium. Phylogenetic analysis proved that the two tested isolates affiliated to (Cobetia amphilecti and Vibrio alginolyticus) with accession numbers of MN099349 and MN099350 respectively. SEM and TEM analysis confirmed the presence of globular particles of insoluble selenium outside and inside the cells of the two selected bacteria. The higher bacterial count in south Safaga compared with wadi Abu Hamrah ensured by drainage pattern which shows that there are main drains that pour directly in mangrove stand especially in south Safaga stand. In conclusion, bacterial isolates can transform toxic selenite to non-toxic red elemental selenium which could be further used for bioremediation of contaminated locations. To our knowledge, these selenite reducing bacteria were not detected and /or isolated from the Egyptian Red Sea coast before as well as both identified strains are novel and well-characterized bacterial aerobic selenite reductase.