Algal cell wall polysaccharides, and their derived oligosaccharides, display a range of health beneficial bioactive properties. Enzymes capable of degrading algal polysaccharides into oligosaccharides may be used to produce biomolecules with new functionalities for the food and pharma industry. Some marine bacteria are specialized in degrading algal biomass and secrete enzymes that can decompose the complex algal cell wall polysaccharides. In order to identify such bacteria and enzymatic activities, we have used a combination of traditional cultivation and isolation methods, bioinformatics and functional screening. This resulted in the discovery of a novel marine bacterium which displays a large enzymatic potential for degradation of red algal polysaccharides e.g. agar and carrageenan. In addition, we searched metagenome sequence data and identified new enzyme candidates for degradation of fucoidan. Enzyme-encoding genes were expressed in E.coli and functionally characterized.