Natural polysaccharides have received much attention due to their wide range of applications. Although most microbial exopolysaccharides (EPSs) use sugars as the major carbon source, such as glucose or sucrose, in this study, EPSs were induced from a squid pen powder (SPP)-containing medium by Paenibacillus mucilaginosus TKU032, a bacterial strain isolated from Taiwanese soil. Under the optimal culture conditions, the maximum EPS yield (14.8 g/L) was obtained. MALDI-TOF MS analysis of an EPS fraction purified by gel filtration revealed two mass peaks with molecular weights of ∼1.05 × 104 and ∼1.35 × 104 Da, respectively. The analysis of the hydrolysates of TKU032 EPS with cellulase, pectinase or α-amylase indicated that the glycosidic bond of TKU032 EPS is most likely an α-1,4 glycosidic bond and the hydrolysates are similar to those of starch. In addition, the purified EPS demonstrated strong antioxidant abilities.