We develop a new methodology best suited to the identification of thermostabilizing mutations for an intrinsically stable membrane protein. The recently discovered thermophilic rhodopsin, whose apparent midpoint temperature of thermal denaturation Tm is measured to be ∼91.8 °C, is chosen as a paradigmatic target. In the methodology, we first regard the residues whose side chains are missing in the crystal structure of the wild type (WT) as the "residues with disordered side chains," which make no significant contributions to the stability, unlike the other essential residues. We then undertake mutating each of the residues with disordered side chains to another residue except Ala and Pro, and the resultant mutant structure is constructed by modifying only the local structure around the mutated residue. This construction is based on the postulation that the structure formed by the other essential residues, which is nearly optimized in such a highly stable protein, should not be modified. The stability changes arising from the mutations are then evaluated using our physics-based free-energy function (FEF). We choose the mutations for which the FEF is much lower than for the WT and test them by experiments. We successfully find three mutants that are significantly more stable than the WT. A double mutant whose Tm reaches ∼100 °C is also discovered.