Potential smoothing, a deterministic analog of stochastic simulated annealing, is a powerful paradigm for the solution of conformational search problems that require extensive sampling, and should be a useful tool in computational approaches to structure prediction and refinement. A novel potential smoothing and search (PSS) algorithm has been developed and applied to predict the packing of transmembrane helices. The highlight of this method is the efficient manner in which it circumvents the combinatorial explosion associated with the large number of minima on multidimensional potential energy surfaces in order to converge to the global energy minimum. Here we show how our potential smoothing and search method succeeds in finding the global minimum energy structure for the glycophorin A (GpA) transmembrane helix dimer by optimizing interhelical van der Waals interactions over rigid and semi-rigid helices. Structures obtained from our ab initio predictions are in close agreement with recent experimental data.