Protein function is acutely sensitive to temperature. Investigations of enzymes have demonstrated that the thermal adaptation of proteins is achieved through adjustments in conformational flexibility that lead to changes in protein function. Subtle changes in primary structure drive these adjustments in tertiary structure and function. Antarctic fish of the Perciformes suborder Notothenioidei survive and thrive in subzero temperatures. Key to the evolutionary success of this group is the adaptation of proteins to the cold environment. Previously, it has been shown that parvalbumin (PV), a non-enzymatic, sarcoplasmic calcium buffer, from Antarctic fish shows a characteristic pattern of thermal sensitivity of calcium binding. At common measurement temperatures, PV from Antarctic fish displays a weaker calcium binding affinity than PVs from temperate counterparts, but at physiological temperatures function is highly conserved. Ancestral sequence reconstruction (ASR) was used to probe the evolutionary trajectory of Antarctic fish PV. Homology modeling was used to view the results of ASR in a three-dimensional context. The evolutionary and modeling results revealed two substitutions at positions 8 and 26 that are most likely to have shifted the function of PV from a temperate Perciformes ancestor to the present thermal sensitivity pattern of extant notothenioids. We hypothesized that these substitutions caused the evolutionary loss of two hydrogen bonds leading to increased conformational flexibility, which, in turn, compensates for the cold environment of the Southern Ocean. Further, we predicted that these single mutations would cause an intermediate shift in calcium binding affinity while the double mutant would show a full conversion of thermal sensitivity pattern to that of a temperate-adapted PV. Functional characterization of the recombinant wild-type protein, two single mutants and double mutant confirmed our hypothesis. Calcium dissociation thermal sensitivity patterns showed an intermediate phenotype for the single mutants and a full right shift to a temperate profile for the double mutant. Furthermore, measurements of calcium rate constants allowed for the development of a structural model, based on the binding energy funnel model, for the shift in calcium binding affinity seen in Antarctic fish PV. Subtle adjustments in the bound and apo-state of PV may lead to the displayed shifts in phenotype. This study revealed the underlying evolutionary steps taken to achieve cold-adaptation of PV found in Antarctic fish.