A novel wild-type recombinant cold-active α-d-galactosidase (α-PsGal) from the cold-adapted marine bacterium Pseudoalteromonas sp. KMM 701, and its mutants D451A and C494N, were studied in terms of their structural, physicochemical, and catalytic properties. Homology models of the three-dimensional α-PsGal structure, its active center, and complexes with D-galactose were constructed for identification of functionally important amino acid residues in the active site of the enzyme, using the crystal structure of the α-galactosidase from Lactobacillus acidophilus as a template. The circular dichroism spectra of the wild α-PsGal and mutant C494N were approximately identical. The C494N mutation decreased the efficiency of retaining the affinity of the enzyme to standard p-nitrophenyl-α-galactopiranoside (pNP-α-Gal). Thin-layer chromatography, matrix-assisted laser desorption/ionization mass spectrometry, and nuclear magnetic resonance spectroscopy methods were used to identify transglycosylation products in reaction mixtures. α-PsGal possessed a narrow acceptor specificity. Fructose, xylose, fucose, and glucose were inactive as acceptors in the transglycosylation reaction. α-PsGal synthesized -α(1→6)- and -α(1→4)-linked galactobiosides from melibiose as well as -α(1→6)- and -α(1→3)-linked p-nitrophenyl-digalactosides (Gal₂-pNP) from pNP-α-Gal. The D451A mutation in the active center completely inactivated the enzyme. However, the substitution of C494N discontinued the Gal-α(1→3)-Gal-pNP synthesis and increased the Gal-α(1→4)-Gal yield compared to Gal-α(1→6)-Gal-pNP.