The primary technique for determining the three-dimensional structure of a protein molecule is X-ray crystallography, from which the molecular replacement (MR) problem often arises as a critical step. The MR problem is a global optimization problem to locate an optimal position of a model protein, whose structure is similar to the unknown protein structure that is to be determined, so that at this position the model protein will produce calculated intensities closest to those observed from an X-ray crystallography experiment. Improving the applicability and robustness of MR methods is an important research topic because commonly used traditional MR methods, though often successful, have their limitations in solving difficult problems. We introduce a new global optimization strategy that combines a coarse-grid search, using a surrogate function, with extensive multi-start local optimization. A new MR code, called SOMoRe, based on this strategy is developed and tested on four realistic problems, including two difficult problems that traditional MR codes failed to solve directly. SOMoRe was able to solve each test problem without any complication, and SOMoRe solved a MR problem using a less complete model than the models required by three other programs. These results indicate that the new method is promising and should enhance the applicability and robustness of the MR methodology.