Alginate, the most abundant carbohydrate presents in brown macroalgae, has recently gained increasing attention as an alternative biomass for the production of biofuel. Oligoalginate lyases catalyze the degradation of alginate oligomers into monomers, a prerequisite for bioethanol production. In this study, two new oligoalginate lyase genes, oalC6 and oalC17, were cloned from Cellulophaga sp. SY116, and expressed them in Escherichia coli. The deduced oligoalginate lyases, OalC6 and OalC17, belonged to the polysaccharide lyase (PL) family 6 and 17, respectively. Both showed less than 50% amino acid identity with all of the characterized oligoalginate lyases. Moreover, OalC6 and OalC17 could degrade both alginate polymers and oligomers into monomers in an exolytic mode. Substrate specificity studies demonstrated that OalC6 preferred α-L-guluronate (polyG) blocks, while OalC17 preferred poly β-D-mannuronate (polyM) blocks. The combination of OalC6 and OalC17 showed synergistic degradation ability toward both alginate polymers and oligomers. Finally, an efficient process for the production of alginate monomers was established by combining the new-isolated exotype alginate lyases (i.e., OalC6 and OalC17) and the endotype alginate lyase AlySY08. Overall, our work provides new insights for the development of novel biotechnologies for biofuel production from seaweed.