Although it is widely appreciated that a functioning innate immune system is required to support multicellular life, we know surprisingly little about how the immune system of early multicellular animals was put together, how it changed over animal evolutionary history or the consequences of those changes for the organism. Here we combine ancestral sequence reconstruction with in vitro molecular-functional analyses and comparative in vivo examinations in mammalian and early-animal model systems to characterize the evolution of the RIG-like receptor (RLR) signaling network, an important component of animal innate antiviral immunity. We find that RLRs originated in the earliest animal lineages, probably through fusion of an RNA-binding domain from Dicer with CARD signaling domains, coupled with the origination of a novel structural fold used for viral RNA recognition. RLRs diversified through gene duplication events followed by changes in domain architecture and adaptively-driven protein-coding changes that repeatedly altered RNA preference. We present evidence that RLRs recruited novel signaling partners at least twice in animal evolution, leading to changes in the RLR signaling network and resulting in alteration of cellular immune function. Our work highlights the dynamic nature of immune-system evolution, the roles that protein structural variants, amino-acid variants and genomic clusters can play in evolving novel protein-protein signaling networks and the potential importance of changes in immune-signaling networks for cellular and organismal function. In our view, further understanding how the innate immune system evolved will help us understand how differences in innate immunity may have contributed to animal biodiversity.