In the process of studying the relationship between marine macroalgae and their bacterial symbionts, we isolated a new species of Rhizobium, which we designated Rhizobium sp. nov. C1 (for "Codium 1"). Here, we report the complete genome sequence of Rhizobium sp. nov. C1.