To obtain an electron-density map from a macromolecular crystal the phase-problem needs to be solved, which often involves the use of heavy-atom derivative crystals and concomitantly the determination of the heavy atom substructure. This is customarily done by direct methods or Patterson-based approaches, which however may fail when only poorly diffracting derivative crystals are available, as often the case for e.g. membrane proteins. Here we present an approach for heavy atom site identification based on a Molecular Replacement Parameter Matrix (MRPM) search. It involves an n-dimensional search to test a wide spectrum of molecular replacement parameters, such as clusters of different conformations. The result is scored by the ability to identify heavy-atom positions, from anomalous difference Fourier maps, that allow meaningful phases to be determined. The strategy was successfully applied in the determination of a membrane protein structure, the CopA Cu+-ATPase, when other methods had failed to resolve the heavy atom substructure. MRPM is particularly suited for proteins undergoing large conformational changes where multiple search models should be generated, and it enables the identification of weak but correct molecular replacement solutions with maximum contrast to prime experimental phasing efforts.