Sponges (Porifera) form symbiotic relationships with specific bacteria while relying on free-living bacteria for nutrition. To explore how sponges discriminate symbiotic from food bacteria, we presented juveniles of the marine demosponge Amphimedon queenslandica with bacterial enrichments from conspecifics and from another species of sponge, and observed their transcriptional and cellular responses. Compared with non-symbionts, symbionts induce a pronounced and transient innate immune response within just 1-2 hours. Also at this time, we observe that three highly conserved transcription factors – nuclear factor kappa-light-chain-enhancer of activated B cells (NF-kB), signal transducer and activator of transcription (STAT) and interferon regulatory factor (IRF) – translocate into the nucleus of amoebocytes and archaeocytes, suggesting that they regulate this transient activation of conserved immunity genes. In contrast, heat-killed symbionts and filtered seawater do not induce nuclear translocation of these transcription factors. The higher expression of these transcription factor genes in amoebocytes further supports their involvement in the immune recognition of symbionts. Given the phylogenetic position of sponges as the likely sister group to all other animals, our findings suggest that a role for innate immunity in regulating animal-bacterial symbiosis is deeply rooted in the origin and early evolution of metazoans.