The authors describe and illustrate two new species of Cryptanthus, C. prolectus and C. proliferus, both endemic to the Atlantic Forest and associated with tree-like Restinga vegetation along the coastal zone of the state of Bahia, Brazil. Despite not being morphologically related to each other, C. prolectus and C. proliferus have in common the simple or subsimple inflorescences, which makes them different from their closer relatives, C. cruzalmensis and C. cajuitensis, respectively. Additional morphological differences are presented, and their geographical occurrence and conservation status are discussed. Illustrations of both species are also provided.