Azotobacter chroococcum H23 (CECT 4435), Azotobacter vinelandii UWD, and Azotobacter vinelandii (ATCC 12837), members of the family Pseudomonadaceae, were used to evaluate their capacity to grow and accumulate polyhydroxyalkanoates (PHAs) using two-phase olive mill wastewater (TPOMW, alpeorujo) diluted at different concentrations as the sole carbon source. The PHAs amounts (g/l) increased clearly when the TPOMW samples were previously digested under anaerobic conditions. The MNR analysis demonstrated that the bacterial strains formed only homopolymers containing beta-hydroxybutyrate, either when grown in diluted TPOMW medium or diluted anaerobically digested TPOMW medium. COD values of the diluted anaerobically digested waste were measured before and after the aerobic PHA-storing phase, and a clear reduction (72%) was recorded after 72 h of incubation. The results obtained in this study suggest the perspectives for using these bacterial strains to produce PHAs from TPOMW, and in parallel, contribute efficiently to the bioremediation of this waste. This fact seems essential if bioplastics are to become competitive products.