Low Energy Electron Diffraction (LEED) is one of the most powerful experimental techniques for surface structure analysis but until now only a trial-and-error approach has been successful. So far, fitting procedures developed to optimize structural and nonstructural parameters-by minimization of the R-factor-have had a fairly small convergence radius, suitable only for local optimization. However, the identification of the global minimum among the several local minima is essential for complex surface structures. Global optimization methods have been applied to LEED structure determination, but they still require starting from structures that are relatively close to the correct one, in order to find the final structure. For complex systems, the number of trial structures and the resulting computation time increase so rapidly that the task of finding the correct model becomes impractical using the present methodologies. In this work we propose a new search method, based on Genetic Algorithms, which is able to determine the correct structural model starting from completely random structures. This method-called here NGA-LEED for Novel Genetic Algorithm for LEED-utilizes bond lengths and symmetry criteria to select reasonable trial structures before performing LEED calculations. This allows a reduction of the parameter space and, consequently of the calculation time, by several orders of magnitude. A refinement of the parameters by least squares fit of simulated annealing is performed only at some intermediate stages and in the final step. The method was successfully tested for two systems, Ag(1 1 1)(4 × 4)-O and Au(1 1 0)-(1 × 2), both in theory versus theory and in theory versus experiment comparisons. Details of the implementation as well as the results for these two systems are presented.