We report here the genome sequences of three Aquimarina megaterium strains isolated from the octocoral Eunicella labiata. We reveal a coding potential for versatile carbon metabolism and biosynthesis of natural products belonging to the polyketide, nonribosomal peptide, and terpene compound classes.