SMC/kleisin complexes form elongated annular structures, which are critical for chromosome segregation, genome maintenance, and the regulation of gene expression. We describe marked structural similarities between bacterial and eukaryotic SMC/kleisin partner proteins (designated here as "kite" proteins for kleisin interacting tandem winged-helix (WH) elements of SMC complexes). Kite proteins are integral parts of all prokaryotic SMC complexes and Smc5/6 but not cohesin and condensin. They are made up of tandem WH domains, form homo- or heterodimers via their amino-terminal WH domain, and they associate with the central part of a kleisin subunit. In placental mammals, the kite subunit NSE3 gave rise to several (>60) kite-related proteins, named MAGE, many of which encode tumor- and testis-specific antigens. Based on architectural rather than sequence similarity, we propose an adapted model for the evolution of the SMC protein complexes and discuss potential functional similarities between bacterial Smc/ScpAB and eukaryotic Smc5/6.