Polyhydroxyalkanoates (PHAs) are linear polyesters synthesized by microbial fermentation of various substrates. PHAs are accumulated in microbial cells in order to store carbon and energy for future use. We used acid-pretreated red alga (Gelidium amansii) as a cheap, abundant carbon source to produce PHA via batch and fed-batch cultivation of Bacillus megaterium KCTC 2194. After acid treatment of 10% (w/v) G. amansii, 25.5 g/L galactose, 3.6 g/L glucose, 6 g/L 5-HMF, and 1.05 g/L levulinic acid were formed. In batch culture at pH 7, the dry cell weight (DCW) and PHA content increased to 5.5 g/L and 51.4%, respectively. The cell concentration was enhanced by fed-batch cultivation using two feeding strategies: pH-stat and intermittent feeding. When the pH-stat feeding strategy was employed to add concentrated hydrolysate to the fermentor, DCW increased to 8.2 g/L, with 53.2% PHA content. When concentrated hydrolysate was fed using the intermittent feeding strategy, higher DCW (10.1 g/L) was obtained, along with a slight increase of PHA content to 54.5%. This study demonstrates that red algae could be used after simple acid treatment, to produce PHA without steps for enzymatic hydrolysis and inhibitor removal.