We describe two new species: Aulospongus trirhabdostylus sp. nov. and Aulospongus mandela sp. nov. from Potiguar Basin (Rio Grande do Norte State, Northeastern Brazil). Both species were compared with their congeners and an identification key for the Atlantic species of Aulospongus is provided. The genus Aulospongus now contains 16 species.