As extended benchmarks to global cluster structure optimization methods, we provide a first systematic point of entry into the world of strongly mixed rare gas clusters. A new set of generalized Lennard‐Jones pair potentials is generated for this purpose, by fitting them to high‐end ab initio reference data. Employing these potentials in our genetic algorithm‐based global structure optimization framework, we examined various systems from binary to quinary mixtures of atom types. A central result from this study is that the famous fcc structure for 38 atoms can survive for certain binary mixtures but appears to be prone to collapsing into the dominating icosahedral structure, which we observed upon introduction of one single atom of a ternary type. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011