We examined variants of an especially cold-active beta-galactosidase (BgaS) to better understand features affecting enzyme activity at temperature extremes. We targeted locations corresponding to a region in the LacZ enzyme previously shown to increase activity and decrease thermostability. Changes in this region of BgaS consistently caused the elimination or reduction of activity. A gene (bgaS3) encoding a loss of function variant was subjected to random mutagenesis to restore activity and discover potential interactions important in cold activity. Gene sequences from the resulting library indicated that only two amino acid alterations, E229D and V405A, were required to restore activity. Genes with combinations of these mutations were constructed and their enzymes purified. Enzymes with the E229D/V405A/G803D alterations (BgaS6), or E229D/V405A (BgaS7) had similar thermal optima and thermostabilities as BgaS. BgaS7, however, showed a 2.5-fold increase in catalytic activity at 15 degrees C and hydrolyzed 80% of lactose in skim milk in less than half the time of BgaS at 2.5 degrees C. Computer-generated models predicted that the substitutions at positions 229 and 405 yielded fewer contacts at the enzyme's activating interface. Results from regional saturation mutagenesis supported this hypothesis and suggested that not easily predicted, subtle, cooperative intramolecular interactions contributed to thermal adaptation.