We report several new global minima for mixed Ar/Xe Lennard-Jones atomic clusters. The geometries deviate significantly from those predicted by the icosahedral packing which dominates the structure of small homogeneous Lennard-Jones clusters. The structural motif common to all the reported structures is the ArXe4 square pyramid. (c) 2005 Elsevier B.V. All rights reserved.