Soft corals (Anthozoa: Octocorallia) are discreet components in the Southwestern Atlantic reef communities. In Brazil, the native octocoral shallow-reef fauna is mostly represented by gorgonians. Consequently, except for the nephtheid Neospongodes atlantica, most of the known soft corals from this region are considered non-indigenous. Hitherto, the monotypic genus Neospongodes, which was proposed in the early 1900s, has been considered to be endemic to the Northeastern Brazilian coast. Herein, based on in situ records, we show that N. atlantica is a substrate generalist that has been probably expanding its distribution by dominating extensive shallow and mesophotic sandy and reef bottoms, generally outcompeting other reef benthic organisms, including Brazilian endemic species. Based on previously unidentified museum specimens, new records, and a broad literature review, we provide the most comprehensive modelling of the potential distribution of this species in the Southwestern Atlantic. Based on molecular inference supported by in-depth morphological analysis, the probable non-indigenous and, therefore, ancient introduction of N. atlantica in Brazilian waters is discussed. Finally, these results support that Neospongodes and the Indo-Pacific Stereonephthya are synonyms, which led us to propose the latter as taxonomically invalid.