Structures of small mixed krypton-xenon clusters of different compositions with an average size of 30–37 atoms are investigated. The Kr 3d 5/2 and Xe 4d 5/2surface core level shifts and photoelectron intensities originating from corner, edge, and face/bulk sites are analyzed by using soft x-ray photoelectron spectroscopy. Structural models are derived from these experiments, which are confirmed by theoretical simulation taking induced dipole interactions into account. It is found that one or two small Xe cores are partly embedded in the surface of the Kr clusters. These may grow and merge leading to a phase separation between the two rare gas moieties in mixed clusters with increasing the Xe content.