This study investigates the marine macroinvertebrate fauna of rhodolith beds (non-geniculated red corallinaceaous algae) in northeast Brazilian. A total of 57 species were identified, belonging to six phyla (Platyhelminthes, Annelida, Sipuncula, Mollusca, Arthropoda and Echinodermata), of which 50 are considered here as new records for the Paraíba State. Annelids (Class Polychaeta) were the most representative taxa in Miramar and Seixas Beaches, while molluscs were dominant in Maceió Beach. This is the first study that includes an identification key, diagnostic features and distribution patterns worldwide and local (including new records) of the marine invertebrate fauna associated with rhodolith beds in northeast Brazil (State of Paraíba). Sampling events were performed in 2018, at low tide in the intertidal to shallow subtidal zones (1.5 and 4.0 m depth), in Miramar, Seixas and Maceió Beaches. A total of 17 species were found for the first time on Seixas Beach, as well as all identified species for Miramar and Maceió. This study tries to contribute to the knowledge of marine invertebrates in northeast Brazilian shallow habitats, providing a baseline for future environmental studies.