A new genus of soft coral from the Republic of Congo is described, Complexum gen. n. Nine West African octocoral species previously described in the genus Alcyonium by Tixier-Durivault (1955) are referred to this new genus, and a new species is described and figured, C. pusillum sp. n. The new species is characterized by having encrusting growth form and abundant spiny clubs in the surface of the polyparium. It colonizes shallow calcareous rocky banks (5 to 20 m depth) existing in coastal water of the region of Pointe-Noire. Based on molecular phylogeny this new genus is well separated from Alcyonium species.