As a low molecular weight alginate, alginate oligosaccharides (AOS) exhibit improved water solubility, better bioavailability, and comprehensive health benefits. In addition, their biocompatibility, biodegradability, non-toxicity, non-immunogenicity, and gelling capability make them an excellent biomaterial with a dual curative effect when applied in a drug delivery system. In this paper, a novel alginate lyase, Algpt, was cloned and characterized from a marine bacterium, Paenibacillus sp. LJ-23. The purified enzyme was composed of 387 amino acid residues, and had a molecular weight of 42.8 kDa. The optimal pH of Algpt was 7.0 and the optimal temperature was 45 °C. The analysis of the conserved domain and the prediction of the three-dimensional structure indicated that Algpt was a novel alginate lyase. The dominant degradation products of Algpt on alginate were AOS dimer to octamer, depending on the incubation time, which demonstrated that Algpt degraded alginate in an endolytic manner. In addition, Algpt was a salt-independent and thermo-tolerant alginate lyase. Its high stability and wide adaptability endow Algpt with great application potential for the efficient preparation of AOS with different sizes and AOS-based products.