Knowledge of the tropical terrestrial cyanobacterial flora from the African continent is still limited. Of 31 strains isolated from soil and subaerial samples collected in Lagos State, Nigeria, three were found to be in the Oculatellaceae, including two species in a new genus. Subsequently, isolates from microbial mats in White Sands National Park in New Mexico, United States, and from a rock near the ocean in Puerto Rico, United States, were found to belong to the new genus as well. Cyanobacterial isolates were characterized microscopically, sequenced for the 16S rRNA gene and associated ITS region, and phylogenetically analyzed. Egbenema gen. nov., with three new species, as well as two new species of Albertania were differentiated from all other Oculatellaceae. Both genera belong to a supported clade within the Oculatellaceae that includes Trichotorquatus and Komarkovaea. The two new species of Albertania, A. egbensis and A. latericola, were from the same sample, but were evolutionarily separate based on 16S rRNA gene phylogenies, percent identity below the 98.7% threshold, and ITS rRNA percent dissimilarity >7.0%. Egbenema aeruginosum gen. et sp. nov. was phylogenetically separated from Trichotorquatus and Albertania but was in a clade with other strains belonging to Egbenema. The two Egbenema strains from the United States are here named Egbenema epilithicum sp. nov. and Egbenema gypsiphilum sp. nov. Our results support the hypothesis that further species discoveries of novel cyanobacteria will likely be made in soils and subaerial habitats, as these habitats continue to be studied, both in tropical and temperate biomes.