In this first attempt to survey the Brazilian sponge-dwelling fishes we present a list of collected fishes, with notes on their distribution, abundance and habitat preferences. Risor ruber, an obligate sponge-dwelling goby, and Scorpaenodes tredecimspinosus, never before collected in association with sponges, are recorded for the first time in the western South Atlantic based on collections made in localities on the northeastern Brazilian coast. Previous work on Risor ruber indicated that it preferred massive sponges, but in our study the majority of the specimens were found in the lumen of tubular sponges, Aplysina lacunosa, together with other fishes and invertebrates, mostly crustaceans. Elacatinus figaro, originally described as a cleaner goby, is also a sponge-dweller that occurs in waters much deeper than previously thought. The sponge community off northeastern Brazil represents the only shelter for several species of fishes in a desert of rubble and flat rocky bottoms, perhaps functioning as habitat ‘oases’. We also found four Brazilian endemic species of fishes associated with sponges in depths greater than 50 m, which contradicts a previous hypothesis suggesting that endemic fishes in Brazilian coastal waters are restricted to depths less than 50 m.