Agar is a major polysaccharide of red algal cells and is mainly decomposed into neoagarobiose by the co-operative effort of β-agarases. Neoagarobiose is hydrolyzed into monomers, d-galactose and 3,6-anhydro-l-galactose, via a microbial oxidative process. Therefore, the enzyme, 1,3-α-3,6-anhydro-l-galactosidase (α-neoagarobiose/neoagarooligosaccharide hydrolase) involved in the final step of the agarolytic pathway is crucial for bioindustrial application of agar. A novel cold-adapted α-neoagarooligosaccharide hydrolase, Ahg786, was identified and characterized from an agarolytic marine bacterium Gayadomonas joobiniege G7. Ahg786 comprises 400 amino acid residues (45.3 kDa), including a 25 amino acid signal peptide. Although it was annotated as a hypothetical protein from the genomic sequencing analysis, NCBI BLAST search showed 57, 58, and 59% identities with the characterized α-neoagarooligosaccharide hydrolases from Saccharophagus degradans 2–40, Zobellia galactanivorans, and Bacteroides plebeius, respectively. The signal peptide-deleted recombinant Ahg786 expressed and purified from Escherichia coli showed dimeric forms and hydrolyzed neoagarobiose, neoagarotetraose, and neoagarohexaose into 3,6-anhydro-l-galactose and other compounds by cleaving α-1,3-glycosidic bonds from the non-reducing ends of neoagarooligosaccharides, as confirmed by thin-layer chromatography and mass spectrometry. The optimum pH and temperature for Ahg786 activity were 7.0 and 15 °C, respectively, indicative of its unique cold-adapted features. The enzymatic activity severely inhibited with 0.5 mM ethylenediaminetetraacetic acid was completely restored or remarkably enhanced by Mn2+ in a concentration-dependent manner, suggestive of the dependence of the enzyme on Mn2+ ions. K
m and V
max values for neoagarobiose were 4.5 mM and 1.33 U/mg, respectively.