Cold-adapted enzymes are characterized both by a higher catalytic activity at low temperatures and by having their temperature optimum down-shifted, compared to mesophilic orthologs. In several cases, the optimum does not coincide with the onset of protein melting but reflects some other type of inactivation. In the psychrophilic α-amylase from an Antarctic bacterium, the inactivation is thought to originate from a specific enzyme-substrate interaction that breaks around room temperature. Here, we report a computational redesign of this enzyme aimed at shifting its temperature optimum upward. A set of mutations designed to stabilize the enzyme-substrate interaction were predicted by computer simulations of the catalytic reaction at different temperatures. The predictions were verified by kinetic experiments and crystal structures of the redesigned α-amylase, showing that the temperature optimum is indeed markedly shifted upward and that the critical surface loop controlling the temperature dependence approaches the target conformation observed in a mesophilic ortholog.