Biobased degradable plastics have received significant attention owing to their potential application as a green alternative to synthetic plastics. A dye-based procedure was used to screen poly-3-hydroxybutyrate (PHB)-producing marine bacteria isolated from the Red Sea, Saudi Arabia. Among the 56 bacterial isolates, Pseudodonghicola xiamenensis, identified using 16S rRNA gene analyses, accumulated the highest amount of PHB. The highest PHB production by P. xiamenensis was achieved after 96 h of incubation at pH 7.5 and 35 °C in the presence of 4% NaCl, and peptone was the preferred nitrogen source. The use of date syrup at 4% (w/v) resulted in a PHB concentration of 15.54 g/L and a PHB yield of 38.85% of the date syrup, with a productivity rate of 0.162 g/L/h, which could substantially improve the production cost. Structural assessment of the bioplastic by Fourier transform infrared spectroscopy and nuclear magnetic resonance spectroscopy revealed the presence of methyl, hydroxyl, methine, methylene, and ester carbonyl groups in the extracted polymer. The derivative products of butanoic acid estimated by gas chromatography-mass spectrometry [butanoic acid, 2-amino-4-(methylseleno), hexanoic acid, 4-methyl-, methyl ester, and hexanedioic acid, monomethyl ester] confirmed the structure of PHB. The present results are the first report on the production of a bioplastic by P. xiamenensis, suggesting that Red Sea habitats are a potential biological reservoir for novel bioplastic-producing bacteria.