Brazil has an extensive and environmentally diverse coastline, which favors the occurrence of numerous cyanobacterial morpho- and ecotypes. Nevertheless, this coastline is still poorly studied and its diversity is underestimated. Considering the family Oscillatoriaceae, Lyngbya deserves special attention. It includes many clades which are phylogenetically non-related but morphologically similar. Such clades occur in marine and freshwater environments and are traditionally treated as a single genus. In the current study, we sampled both mediolittoral and estuarine zones along the Brazilian coast. Based on a polyphasic characterization, we described a new genus of marine filamentous cyanobacteria: Neolyngbya. It includes six new species sampled in Brazil, which are described in this study (N. maris-brasilis, N. granulosa, N. irregularis, N. nodulosa, N. arenicola and N. tenuis). Additionally, the characterization included a Neolyngbya sp. from Japan in the clade, but only based on molecular data. All species presented irregular arrangement of thylakoids as described for Oscillatoriaceae. The new genus shares morphological characteristics with species in different clades of the Lyngbya complex. The ultrastructural analyses of Neolyngbya, however, showed numerous gas vesicles, especially in the interthylakoid space; such feature is not observed in benthic Lyngbya species. Neolyngbya formed a well-supported clade (16S rRNA phylogeny), however distantly related to L. aestuarii and L. confervoides, both marine species clusters. The Limnoraphis clade is in a sister relationship to the Neolyngbya clade, however the former occurs in freshwater plankton. Secondary structures of 16S-23S rRNA ITS sequences were congruent with the phylogeny. The polyphasic characterization was helpful to clarify the diversity and ecological aspects of benthic filamentous cyanobacteria and the evolutionary history of the group. This favors a better understanding of inter and infrageneric taxa. The number of novel taxa described in this study emphasizes the importance of conducting additional floristic surveys, mainly in underexplored marine environments, to reveal the real cyanobacterial biodiversity in these areas.