Agar, a major polysaccharide of red algal cells, is degraded by β-agarases into neoagarobiose, which is further hydrolyzed into the monomers, d-galactose and 3,6-anhydro-l-galactose, by 1,3-α-3,6-anhydro-l-galactosidases including α-1,3-l-neoagarooligasaccharide hydrolase (α-NAOSH). A novel cold-adapted alkaline α-NAOSH, Ahg558, consisting of 359 amino acids (40.8 kDa) was identified from Gayadomonas joobiniege G7. It was annotated as a glycosyl hydrolase family 43 based on genomic sequence analysis, showing 84% and 74% identities with the characterized α-NAOSHs from Agarivorans gilvus WH0801 and Saccharophagus degradans 2–40, respectively. The recombinant Ahg558 (rAhg558) purified from Escherichia coli formed dimers and cleaved α-1,3 glycosidic bonds at the non-reducing ends of the neoagarobiose, neoagarotetraose, and neoagarohexaose, which was confirmed by thin-layer chromatography and mass spectrometry. The optimum pH and temperature for rAhg558 activity were 9.0 and 30 °C, respectively. Unusually, it retained over 93% activity in a broad range of temperatures between 0 and 40 °C and over 73% in a broad range of pH between pH 6.0 and pH 9.0, indicating it is a unique cold-adapted alkaline exo-acting α-NAOSH. Its enzymatic activity was dependent on Mn2+ ions. K
m and V
max values toward neoagarobiose were 2.6 mg/mL (8.01 mM) and 133.33 U/mg, respectively.