Abstract The Rel/NF-κB transcription factor family has myriad roles in immunity, development, and differentiation in animals, and was considered a key innovation for animal multicellularity. Rel homology domain-containing proteins were previously hypothesized to have originated in a last common ancestor of animals and some of their closest unicellular relatives. However, key taxa were missing from previous analyses, necessitating a systematic investigation into the distribution and evolution of these proteins. Here, we address this knowledge gap by surveying taxonomically broad data from eukaryotes, with a special emphasis on lineages closely related to animals. We report an earlier origin for Rel/NF-κB proteins than previously described, in the last common ancestor of animals and fungi, and show that even in the sister group to fungi, these proteins contain elements that in animals are necessary for the subcellular regulation of Rel/NF-κB.