Prokaryotic histone-like proteins (Hlps) are abundant proteins found in bacterial and plastid nucleoids. Hlps are also found in the eukaryotic dinoflagellates and the apicomplexans, two major lineages of the Alveolata. It may be expected that Hlps of both groups were derived from the same ancestral Alveolates. However, our phylogenetic analyses suggest different origins for the dinoflagellate and the apicomplexan Hlps. The apicomplexan Hlps are affiliated with the cyanobacteria and probably originated from Hlps of the plastid genome. The dinoflagellate Hlps and the proteobacterial long Hlps form a clade that branch off from the node with the proteobacterial short Hlps.