Polyhydroxyalkanoates (PHAs) are green and sustainable bioplastics that could replace petrochemical synthetic plastics without posing environmental threats to living organisms. In addition, sustainable PHA production could be achieved using marine photosynthetic purple nonsulfur bacteria (PNSBs) that utilize natural seawater, sunlight, carbon dioxide gas, and nitrogen gas for growth. However, PHA production using marine photosynthetic PNSBs has not been economically feasible yet due to its high cost and low productivity. In this work, strain improvement, using genome-wide mutagenesis coupled with high-throughput screening via fluorescence-activated cell sorting, we were able to create Rhodovulum sulfidophilum mutants with enhanced volumetric PHA productivity, with an up to 1.7-fold increase. The best selected mutants (E6 and E6M4) reached the stationary growth phase 1 day faster and accumulated the maximum PHA content 2 days faster than the wild type. Maximizing volumetric PHA productivity before the stationary growth phase is indeed an additional advantage for R. sulfidophilum as a growth-associated PHA producer.