Posttranslational histone modifications modulate chromatin-templated processes in various biological systems. H4K20 methylation is considered to have an evolutionarily ancient role in DNA repair and genome integrity, while its function in heterochromatin function and gene expression is thought to have arisen later during evolution. Here, we identify and characterize H4K20 methylases of the Set8 family in Plasmodium and Toxoplasma, two medically important members of the protozoan phylum Apicomplexa. Remarkably, parasite Set8-related proteins display H4K20 mono-, di-, and trimethylase activities, in striking contrast to the monomethylase-restricted human Set8. Structurally, few residues forming the substrate-specific channel dictate enzyme methylation multiplicity. These enzymes are cell cycle regulated and focally enriched at pericentric and telomeric heterochromatin in both parasites. Collectively, our findings provide new insights into the evolution of Set8-mediated biochemical pathways, suggesting that the heterochromatic function of the marker is not restricted to metazoans. Thus, these lower eukaryotes have developed a diverse panel of biological stages through their high capacity to differentiate, and epigenetics only begins to emerge as a strong determinant of their biology.