Virus-derived sequences and transposable elements constitute a substantial portion of many cellular genomes. Recent insights reveal the intimate evolutionary relationship between these sequences and various cellular immune pathways. At the most basic level, superinfection exclusion may be considered a prototypical virus-mediated immune system that has been described in both prokaryotes and eukaryotes. More complex immune mechanisms fully or partially derived from mobile genetic elements include CRISPR-Cas of prokaryotes and the RAG1/2 system of vertebrates, which provide immunological memory of foreign genetic elements and generate antibody and T cell receptor diversity, respectively. In this review, we summarize the current knowledge on the contribution of mobile genetic elements to the evolution of cellular immune pathways. A picture is emerging in which the various cellular immune systems originate from and are spread by viruses and transposable elements. Immune systems likely evolved from simple superinfection exclusion to highly complex defense strategies.