We explore the effects of thermostats in replica exchange molecular dynamics (REMD) simulations. For thermostats that do not produce a canonical ensemble, REMD simulations are found to distort the configuration-space distributions. For bulk water, we find small deviations of the average potential energies, the buildup of tails in the potential energy distributions, and artificial correlations between the energies at different temperatures. If a solute is present, as in protein folding simulations, its conformational equilibrium can be altered. In REMD simulations of a helix-forming peptide with a weak-coupling (Berendsen) thermostat, we find that the folded state is overpopulated by about 10% at low temperatures, and underpopulated at high temperatures. As a consequence, the enthalpy of folding deviates by almost 3 kcal/mol from the correct value. The reason for this population shift is that non-canonical ensembles with narrowed potential energy fluctuations artificially bias toward replica exchanges between low-energy folded structures at the high temperature and high-energy unfolded structures at the low temperature. We conclude that REMD simulations should only be performed in conjunction with thermostats that produce a canonical ensemble.