The primary technique for determining the three-dimensional structure of a protein is X-ray crystallography, in which the molecular replacement (MR) problem arises as a critical step. Knowledge of protein structures is extremely useful for medical research, including discovering the molecular basis of disease and designing pharmaceutical drugs. This thesis proposes a new strategy to solve the MR problem, which is a global optimization problem to find the optimal orientation and position of a structurally similar model protein that will produce calculated intensities closest to those observed from an X-ray crystallography experiment. Improving the applicability and the robustness of MR methods is an important research goal because commonly used traditional MR methods, though often successful, have difficulty solving certain classes of MR problems. Moreover, the use of MR methods is only expected to increase as more structures are deposited into the Protein Data Bank. The new strategy has two major components: a six-dimensional global search and multi-start local optimization. The global search uses a low-frequency surrogate objective function and samples a coarse grid to identify good starting points for multi-start local optimization, which uses a more accurate objective function. As a result, the global search is relatively quick and the local optimization efforts are focused on promising regions of the MR variable space where solutions are likely to exist, in contrast to the traditional search strategy that exhaustively samples a uniformly fine grid of the variable space. In addition, the new strategy is deterministic, in contrast to stochastic search methods that randomly sample the variable space. This dissertation introduces a new MR program called SOMoRe that implements the new global optimization strategy. When tested on seven problems, SOMoRe was able to straightforwardly solve every test problem, including three problems that could not be directly solved by traditional MR programs. Moreover, SOMoRe also solved a MR problem using a less complete model than those required by two traditional programs and a stochastic six-dimensional program. Based on these results, this new strategy promises to extend the applicability and robustness of MR.