Although the presence and important physiological roles of bacterial symbionts in marine invertebrates are increasingly recognized, much of the fundamental knowledge on these bacterial symbionts remain to be explored. Crown-of-thorns starfish, a primary predator of reef-building corals in the Indo-Pacific Ocean, is also known to harbor bacterial symbionts. Here we show that a single bacterium (named COTS27) is densely and predominantly populated in the subcuticular space of the entire body surface of Crown-of-thorns starfish by forming a biofilm like structure. COTS27 belongs to a bacterial clade that presumably represent a distinct order (referred to as marine spirochetes) in the phylum Spirochaetes, and is universally associated with Crown-of-thorns starfish across the Indo-Pacific Ocean. The genome sequence of COTS27, reconstituted from the hologenome sequence data of Crown-of-thorns starfish, infers the biological features of COTS27, including genetic traits probably linked to adaptation to marine environments and the evolution as an extracellular endosymbiont in the subcuticular space. Preliminary experiments implied metabolic change with and without these bacteria. The universal and nearly mono-specific association of COTS27 with Crown-of-thorns starfish could be a useful model to study the symbiont-host interactions in marine invertebrates.