Marine microbes are a rich source of enzymes for the degradation of diverse polysaccharides. Paraglaciecola hydrolytica S66T is a marine bacterium capable of hydrolyzing polysaccharides found in the cell wall of red macroalgae. In this study, we applied an approach combining genomic mining with functional analysis to uncover the potential of this bacterium to produce enzymes for the hydrolysis of complex marine polysaccharides. A special feature of P. hydrolytica S66T is the presence of a large genomic region harboring an array of carbohydrate-active enzymes (CAZymes) notably agarases and carrageenases. Based on a first functional characterization combined with a comparative sequence analysis, we confirmed the enzymatic activities of several enzymes required for red algal polysaccharide degradation by the bacterium. In particular, we report for the first time, the discovery of novel enzyme activities targeting furcellaran, a hybrid carrageenan containing both β-carrageenan and κ/β-carrageenan motifs. Some of these enzymes represent a new subfamily within the CAZy classification. From the combined analyses, we propose models for the complete degradation of agar and κ/β-type carrageenan by P. hydrolytica S66T. The novel enzymes described here may find value in new bio-based industries and advance our understanding of the mechanisms responsible for recycling of red algal polysaccharides in marine ecosystems.