We present a computationally efficient semi-empirical method, based on standard first-principles techniques and the so-called virtual crystal approximation, for determining the average atomic structure of crystals with substitutional disorder. We show that, making use of a minimal amount of experimental information, it is possible to define convenient figures of merit that allow us to recast the determination of the average atomic ordering within the unit cell as a minimization problem. We have tested our approach by applying it to a wide variety of materials, ranging from oxynitrides to borocarbides and transition-metal perovskite oxides. In all the cases we were able to reproduce the experimental solution, when it exists, or the first-principles result obtained by means of much more computationally intensive approaches. © 2010 IOP Publishing Ltd.