We present a new replica exchange method, designed for optimal native state protein sampling in explicit solvent, called replica exchange with flexible tempering (REFT). The method was built upon the recently introduced replica exchange with solute tempering (REST). The potential function is adapted to direct the conformational search toward interdomain movements and the flexible portions of the protein. We demonstrate the improved sampling efficiency of REFT compared to the original REST for the bacteriophage T4 lysozyme.