Poly-3-hydroxyalkanoic acids (PHAs) are bacterial storage polymers commonly used in bioplastic production. Halophilic bacteria are industrially interesting organisms, as their salinity tolerance and psychrophilic nature lowers sterility requirements and subsequent production costs. We investigated PHA synthesis in two bacterial strains, Halomonas sp. 363 and Paracoccus sp. 392, isolated from Southern Ocean sea ice and elucidated the related PHA biopolymer accumulation and composition with various approaches, such as transcriptomics, microscopy, and chromatography. We show that both bacterial strains produce PHAs at 4°C when the availability of nitrogen and/or oxygen limited growth. The genome of Halomonas sp. 363 carries three phaC synthase genes and transcribes genes along three PHA pathways (I to III), whereas Paracoccus sp. 392 carries only one phaC gene and transcribes genes along one pathway (I). Thus, Halomonas sp. 363 has a versatile repertoire of phaC genes and pathways enabling production of both short- and medium-chain-length PHA products. IMPORTANCE Plastic pollution is one of the most topical threats to the health of the oceans and seas. One recognized way to alleviate the problem is to use degradable bioplastic materials in high-risk applications. PHA is a promising bioplastic material as it is nontoxic and fully produced and degraded by bacteria. Sea ice is an interesting environment for prospecting novel PHA-producing organisms, since traits advantageous to lower production costs, such as tolerance for high salinities and low temperatures, are common. We show that two sea-ice bacteria, Halomonas sp. 363 and Paracoccus sp. 392, are able to produce various types of PHA from inexpensive carbon sources. Halomonas sp. 363 is an especially interesting PHA-producing organism, since it has three different synthesis pathways to produce both short- and medium-chain-length PHAs.