A small change in the Hamiltonian scaling in Replica Exchange with Solute Tempering (REST) is found to improve its sampling efficiency greatly, especially for the sampling of aqueous protein solutions in which there are large-scale solute conformation changes. Like the original REST (REST1), the new version (which we call REST2) also bypasses the poor scaling with system size of the standard Temperature Replica Exchange Method (TREM), reducing the number of replicas (parallel processes) from what must be used in TREM. This reduction is accomplished by deforming the Hamiltonian function for each replica in such a way that the acceptance probability for the exchange of replica configurations does not depend on the number of explicit water molecules in the system. For proof of concept, REST2 is compared with TREM and with REST1 for the folding of the trpcage and β-hairpin in water. The comparisons confirm that REST2 greatly reduces the number of CPUs required by regular replica exchange and greatly increases the sampling efficiency over REST1. This method reduces the CPU time required for calculating thermodynamic averages and for the ab initio folding of proteins in explicit water.