Monellin is a highly potent sweet-tasting protein but relatively little is known about how it interacts with the sweet taste receptor. We determined X-ray crystal structures of 3 single-chain monellin (MNEI) proteins with alterations at 2 core residues (G16A, V37A, and G16A/V37A) that induce 2- to 10-fold reductions in sweetness relative to the wild-type protein. Surprisingly, no changes were observed in the global protein fold or the positions of surface amino acids important for MNEI sweetness that could explain these differences in protein activity. Differential scanning calorimetry showed that while the thermal stability of each mutant MNEI was reduced, the least sweet mutant, G16A-MNEI, was not the least stable protein. In contrast, solution spectroscopic measurements revealed that changes in protein flexibility and the C-terminal structure correlate directly with protein activity. G16A mutation-induced disorder in the protein core is propagated via changes to hydrophobic interactions that disrupt the formation and/or position of a critical C-terminal poly-(L-proline) II helix. These findings suggest that MNEI interaction with the sweet taste receptor is highly sensitive to the relative positions of key residues across its protein surface and that loss of sweetness in G16A-MNEI may result from an increased entropic cost of binding.