Complex intermetallic compounds (CIMCs) with bulk cage-like structures are a class of ordered alloys made of highly symmetric polyhedra as building blocks. Representatives of this family includes quasicrystals and their approximants, as well as intermetallic clathrates and related compounds with large crystal cells. Their unique structures can lead to unusual surface properties – at least when compared to those of conventional alloys -- which make them attractive for a number of applications, like efficient coatings, templates for building new molecular nano-structures or as novel catalytic materials. The detailed knowledge of surface structures is a necessary step to understand and tune the surface structure-property relationships. In this talk I will show that Density Functional Theory calculations, possibly combined with experimental surface science techniques, can be used to determine the thermodynamic, atomic and electronic structures of the CIMC stable surfaces. I will discuss the influence of the intrinsic bulk properties of the compounds, on their surfaces structures and properties.