Rhynchonema Cobb, 1920 is a genus with worldwide distribution. It is found in diverse coastal environments ranging from brackish water to exposed beaches in intertidal and low subtidal zones, from clay to coarse sand and in sediments under seagrass beds. In this study we describe two new tropical species from Northeast South America: Rhynchonema cemae sp.n. and R. veronicae sp. n. from Olinda’s Isthmus, Pernambuco, Brazil. These two species are mainly characterized by the shapes of the spicules and gubernaculum, which are described here for the first time. The two species can be differentiated primarily on the basis of the spicules, which in R. cemae are symmetrical, fine and long, while in R. veronicae they are asymmetrical, more robust and shorter. We describe for the first time the presence of Rhynchonema species on the east side of South America and provide a review of the genus and a polytomous identification key. Our review of the literature and construction of a polytomous key demonstrated that most of the species descriptions are incomplete.