Background : Many large secreted gel-forming mucins contain multiple copies of a "naked" cysteine-enriched domain (CYS domain) that interrupt or are adjacent to mucin domains (Ser/Thr/Pro regions). There is less similarity of homologous CYS sequences between species than there is across CYS repeats within species. These CYS domains are likely implicated in reversible mucin-mucin interactions that play a central role in mucus properties. Results : The use of multiple genome sequences in a comparative analysis of CYS sequences identified new mucins containing the CYS domain in various species. Furthermore, analysis showed that this domain is at least 650 million-year old and that CYS sequences evolved under strong selective pressure in concerted fashion in all species examined by two mechanisms that never coexist within a given gene: either multiplication of exons encoding CYS modules or successive intra-exonic duplications. Conclusion : The CYS sequences appear to have undergone concerted evolution with a high selective pressure to conserve cysteine and other amino acid residues. This domain is the best-conserved domain in secreted mucins pointing toward an important common function in many different organisms.