Enzymatic hydrolysis of sodium alginate to produce alginate oligosaccharides has drawn increasing attention due to its advantages of containing a wild reaction condition, excellent gel properties and specific products easy for purification. However, the efficient commercial enzyme tools are rarely available. A new alginate lyase with high activity (24,038 U/mg) has been purified from a newly isolated marine strain, Cellulophaga sp. NJ-1. The enzyme was most active at 50 °C and pH 8.0 and maintained stability at a broad pH range (6.0–10.0) and temperature below 40 °C. It had broad substrate specificity toward sodium alginate, heteropolymeric MG blocks (polyMG), homopolymeric M blocks (polyM) and homopolymeric G blocks (polyG), and possessed higher affinity toward polyG (15.63 mM) as well as polyMG (23.90 mM) than polyM (53.61 mM) and sodium alginate (27.21 mM). The TLC and MS spectroscopy analysis of degradation products suggested that it completely hydrolyzed sodium alginate into oligosaccharides of low degrees of polymerization (DPs). The excellent properties would make it a promising tool for full use of sodium alginate to produce oligosaccharides.