Microbes have been critical drivers of evolutionary innovation in animals. To understand the processes that influence the origin of specialized symbiotic organs, we report the sequencing and analysis of the genome of Euprymna scolopes, a model cephalopod with richly characterized host-microbe interactions. We identified large-scale genomic reorganization shared between E. scolopes and Octopus bimaculoides and posit that this reorganization has contributed to the evolution of cephalopod complexity. To reveal genomic signatures of host-symbiont interactions, we focused on two specialized organs of E. scolopes: the light organ, which harbors a monoculture of Vibrio fischeri, and the accessory nidamental gland (ANG), a reproductive organ containing a bacterial consortium. Our findings suggest that the two symbiotic organs within E. scolopes originated by different evolutionary mechanisms. Transcripts expressed in these microbe-associated tissues displayed their own unique signatures in both coding sequences and the surrounding regulatory regions. Compared with other tissues, the light organ showed an abundance of genes associated with immunity and mediating light, whereas the ANG was enriched in orphan genes known only from E. scolopes Together, these analyses provide evidence for different patterns of genomic evolution of symbiotic organs within a single host.