Determination of the atomic structure of solid surfaces typically depends on comparison of measured properties with simulations based on hypothesized structural models. For simple structures, the models may be guessed, but for more complex structures there is a need for reliable theory-based search algorithms. So far, such methods have been limited by the combinatorial complexity and computational expense of sufficiently accurate energy estimation for surfaces. However, the introduction of machine learning methods has the potential to change this radically. Here, we demonstrate how an evolutionary algorithm, utilizing machine learning for accelerated energy estimation and diverse population generation, can be used to solve an unknown surface structure—the (4×4) surface oxide on Pt3Sn(111)–based on limited experimental input. The algorithm is efficient and robust, and should be broadly applicable in surface studies, where it can replace manual, intuition based model generation.