This study investigated the putative effects of co-cultivation of Euglena gracilis with Pseudoalteromonas sp. MEBiC 03485 on the growth of E. gracilis and its paramylon production. The strain MEBiC 03485 had beneficial effects on the growth and paramylon contents of E. gracilis. To determine the optimal conditions for co-cultivation, the effects of algal to bacterial inoculum ratios and E. gracilis growth stages were examined. Under optimal conditions, the biomass productivity and paramylon production were increased by more than 23% and 34%, respectively. These effects were attributed to the extracellular polymeric substances (EPS) from the strain MEBiC 03485. GC-MS and HPAEC were carried out to analyze the composition of EPS. It was found that the EPS consisted of rhamnose, galactose, glucose, and mannose. These results suggest a novel approach for potentially enhancing the growth of E. gracilis as well as its paramylon production, via co-culturing with the symbiotic strain MEBiC 03485.