A gene coding for a novel putative amylase, oligo-1,6-glucosidase from a psychrotrophic bacterium Exiguobacterium sibiricum from Siberian permafrost soil was cloned and expressed in Escherichia coli. The amino acid sequence of the predicted protein EsOgl and its 3D model displayed several features characteristic for the cold-active enzymes while possessing an unusually high number of proline residues in the loops—a typical feature of thermophilic enzymes. The activity of the purified recombinant protein was tested with p-nitrophenyl α-D-glucopyranoside as a substrate. The enzyme displayed a plateau-shaped temperature-activity profile with the optimum at 25 °C and a pronounced activity at low temperatures (50% of maximum activity at 5 °C). To improve the thermal stability at temperatures above 40 °C, we have introduced proline residues into four positions of EsOgl by site-directed mutagenesis according to “the proline rule”. Two of the mutants, S130P and A109P demonstrated a three- and two-fold increased half-life at 45 °C. Moreover, S130P mutation led to a 60% increase in the catalytic rate constant. Combining the mutations resulted in a further increase in stability transforming the temperature-activity profile to a typical mesophilic pattern. In the most thermostable variant A109P/S130P/E176P, the half-life at 45 °C was increased from 11 min (wild-type) to 129 min.