Stochastic search algorithms can be used to perform rapid six-dimensional molecular-replacement searches. A molecular-replacement procedure has been developed that uses an evolutionary algorithm to simultaneously optimize the orientation and position of a search model in a unit cell. Here, the performance of this algorithm and its dependence on search model quality and choice of target function are examined. Although the evolutionary search procedure is capable of finding solutions with search models that represent only a small fraction of the total scattering matter of the target molecule, the efficiency of the search procedure is highly dependent on the quality of the search model. Polyalanine models frequently provide better search efficiency than all-atom models, even in cases where the side-chain positions are known with high accuracy. Although the success of the search procedure is not highly dependent on the statistic used as the target function, the correlation coefficient between observed and calculated structure-factor amplitudes generally results in better search efficiency than does the R factor. An alternative stochastic search procedure, simulated annealing, provides similar overall performance to evolutionary search. Methods of extending the evolutionary search algorithm to include internal optimization, selection and construction of the search model are now beginning to be investigated.