The Rel/nuclear factor-kappa B (NF-kappaB) and nuclear factor of activated T-cells (NFAT) transcription factors contribute to the regulation of an assortment of biological processes by binding DNA with high specificity using their Rel homology domain (RHD). Recently, it has been shown that members of these gene families are present in the genome of the anthozoan cnidarian Nematostella vectensis, indicating that they predate the evolution of the most recent ancestor to living bilaterians. By identifying a single NF-kappaB gene in the genome of the demosponge Amphimedon queenslandica, a representative of an even earlier branching metazoan lineage, we demonstrate here that the Rel/NF-kappaB family originated at the dawn of the Metazoa. There is no evidence of RHDs in fungal and choanoflagellate genomes, supporting the notion that the RHD is a metazoan-specific innovation. The A. queenslandica gene (AmqNF-kappaB) encodes a protein that is highly similar in structure to the vertebrate NF-kappaB p50/p52 proteins, possessing both a RHD and ankyrin (ANK) repeats. The intact AmqNF-kappaB contrasts with the N. vectensis NF-kappaB, which lacks ANK repeats, and suggests that the ancestral metazoan NF-kappaB was configured identically to contemporary vertebrate and sponge forms. AmqNF-kappaB is expressed during A. queenslandica embryogenesis, suggesting a developmental role.