Sabah, Malaysia, is well known for its extensive and diverse coral reefs. It is located on the northwestern edge of the Coral Triangle, the region with the highest marine biodiversity. Much of the marine fauna here is still unknown, especially inconspicuous animals, such as small stoloniferous octocorals, which are common on coral reefs. Here, we describe two new monospecific genera of the family Arulidae found off the coast of Kota Kinabalu, Sabah, East Malaysia; Bunga payung gen. nov. et sp. nov. and Laeta waheedae gen. nov. et sp. nov. As well, the stoloniferan genus Phenganax Alderslade & McFadden, 2011 belonging to the family Clavulariidae is expanded with three new species, P. marumi sp. nov., P. subtilis sp. nov., and P. stokvisi sp. nov., which are all sclerite-free. Additionally, we report a possibly undescribed species, closely related to the clavulariid genera Azoriella Lopez-Gonzalez & Gili, 2001 and Cervera Lopez-Gonzalez et al., 1995. As this and other recent studies have shown, discoveries of small stoloniferous octocorals are helping to fill gaps in our knowledge of the overall systematics of Octocorallia.