In the course of both innate and adaptive immunity, cytidine deaminases within the activation induced cytidine deaminase (AID)/apolipoprotein B editing complex (APOBEC) family modulate immune responses by mutating specific nucleic acid sequences of hosts and pathogens. The evolutionary emergence of these mediators, however, seems to coincide precisely with the emergence of adaptive immunity in vertebrates. Here, we show a family of genes in species within two divergent invertebrate phyla-the echinoderm Strongylocentrotus purpuratus and the brachiopod Lingula anatina-that encode proteins with similarities in amino acid sequence and enzymatic activities to the vertebrate AID/APOBECs. The expression of these invertebrate factors is enriched in tissues undergoing constant, direct interactions with microbes and can be induced upon pathogen challenge. Our findings suggest that AID/APOBEC proteins, and their function in immunity, emerged far earlier than previously thought. Thus, cytidine deamination is probably an ancient innate immune mechanism that predates the protostome/deuterostome divergence.