Protozoan parasites have tremendously diverse lifestyles that require adaptation to a remarkable assortment of different environmental conditions. In order to complete their life cycles, protozoan parasites rely on fine-tuning gene expression. In general, protozoa use novel regulatory elements, transcription factors, and epigenetic mechanisms to regulate their transcriptomes. One of the most surprising findings includes the nature of their histones - these primitive eukaryotes lack some histones yet harbor novel histone variants of unknown function. In this review, we describe the histone components of different protozoan parasites based on literature and database searching. We summarize the key discoveries regarding histones and histone variants and their impact on chromatin regulation in protozoan parasites. In addition, we list histone genes IDs, sequences, and genomic localization of several protozoan parasites and Microsporidia histones, obtained from a thorough search of genome databases. We then compare these findings with those observed in higher eukaryotes, allowing us to highlight some novel aspects of epigenetic regulation in protists and to propose questions to be addressed in the upcoming years.