The conformational heterogeneity of a folded protein can affect not only its function but also stability and folding. We recently discovered and characterized a stabilized double mutant (L49I/I57V) of the protein CI2 and showed that state-of-the-art prediction methods could not predict the increased stability relative to the wild-type protein. Here, we have examined whether changed native-state dynamics, and resulting entropy changes, can explain the stability changes in the double mutant protein, as well as the two single mutant forms. We have combined NMR relaxation measurements of the ps-ns dynamics of amide groups in the backbone and the methyl groups in the side chains with molecular dynamics simulations to quantify the native-state dynamics. The NMR experiments reveal that the mutations have different effects on the conformational flexibility of CI2: a reduction in conformational dynamics (and entropy estimated from this) of the native state of the L49I variant correlates with its decreased stability, while increased dynamics of the I57V and L49I/I57V variants correlates with their increased stability. These findings suggest that explicitly accounting for changes in native-state entropy might be needed to improve the predictions of the effect of mutations on protein stability.