Sponges form symbiotic relationships with diverse and abundant microbial communities. Cyanobacteria are among the most important members of the microbial communities that are associated with sponges. Here, we performed a genus-wide comparative genomic analysis of the newly described marine benthic cyanobacterial genus Leptothoe (Synechococcales). We obtained draft genomes from Le. kymatousa TAU-MAC 1615 and Le. spongobia TAU-MAC 1115, isolated from marine sponges. We identified five additional Leptothoe genomes, host-associated or free-living, using a phylogenomic approach, and the comparison of all genomes showed that the sponge-associated strains display features of a symbiotic lifestyle. Le. kymatousa and Le. spongobia have undergone genome reduction; they harbored considerably fewer genes encoding for (i) cofactors, vitamins, prosthetic groups, pigments, proteins, and amino acid biosynthesis; (ii) DNA repair; (iii) antioxidant enzymes; and (iv) biosynthesis of capsular and extracellular polysaccharides. They have also lost several genes related to chemotaxis and motility. Eukaryotic-like proteins, such as ankyrin repeats, playing important roles in sponge-symbiont interactions, were identified in sponge-associated Leptothoe genomes. The sponge-associated Leptothoe stains harbored biosynthetic gene clusters encoding novel natural products despite genome reduction. Comparisons of the biosynthetic capacities of Leptothoe with chemically rich cyanobacteria revealed that Leptothoe is another promising marine cyanobacterium for the biosynthesis of novel natural products.