Molecular dynamics simulated annealing (SA-MD) simulations are frequently used for refinement and optimization of peptide and protein structures. Depending on the simulation conditions and simulation length SA-MD simulations can be trapped in locally stable conformations far from the global optimum. As an alternative replica exchange molecular dynamics (RexMD) simulations can be used which allow exchanges between high and low simulation temperatures at all stages of the simulation. A significant drawback of RexMD simulations is, however, the rapid increase of the replica number with increasing system size to cover a desired temperature range. A combined SA-MD and RexMD approach termed SA-RexMD is suggested that employs a small number of replicas (4) and starts initially with a set of high simulation temperatures followed by gradual cooling of the set of temperatures until a target temperature has been reached. The protocol has been applied for the folding of several peptide systems and for the refinement of protein model structures. In all the cases, the SA-RexMD method turned out to be significantly more efficient in reaching low energy structures and also structures close to experiment compared to continuous MD simulations at the target temperature and to SA-MD simulations at the same computational demand. The approach is well suited for applications in structure refinement and for systematic force field improvement. (C) 2009 Elsevier Inc. All rights reserved.