The evolutionary aspects of cystatins are greatly underexplored in early-emerging metazoans. Thus, we surveyed the gene organization, protein architecture, and phylogeny of cystatin homologues mined from 110 genomes and the transcriptomes of 58 basal metazoan species, encompassing free-living and parasite taxa of Porifera, Placozoa, Cnidaria (including Myxozoa), and Ctenophora. We found that the cystatin gene repertoire significantly differs among phyla, with stefins present in most of the investigated lineages but with type 2 cystatins missing in several basal metazoan groups. Similar to liver and intestinal flukes, myxozoan parasites possess atypical stefins with chimeric structure that combine motifs of classical stefins and type 2 cystatins. Other early metazoan taxa regardless of lifestyle have only the classical representation of cystatins and lack multi-domain ones. Our comprehensive phylogenetic analyses revealed that stefins and type 2 cystatins clustered into taxonomically defined clades with multiple independent paralogous groups, which probably arose due to gene duplications. The stefin clade split between the subclades of classical stefins and the atypical stefins of myxozoans and flukes. Atypical stefins represent key evolutionary innovations of the two parasite groups for which their origin might have been linked with ancestral gene chimerization, obligate parasitism, life cycle complexity, genome reduction, and host immunity.