Here we describe two new species in the genus Branchiosyllis Ehlers, 1887 associated with sponges. Branchiosyllis belchiori sp. nov. was found in Todos os Santos Bay, state of Bahia, and in the Fernando de Noronha Island (Northeastern Brazil), and Branchiosyllis gonzaguinhai sp. nov. was found in the Fernando de Noronha Island and Rocas Atoll. We compare the species herein described with their morphologically most similar congeners and provide a synoptic table of the morphological variation among the type-series of the two new species. An identification key for the species of Branchiosyllis recorded in Brazil is also provided.