Two new species of bryozoans encrusting subtidal rocks are described from the shallow waters of Madeira Island. We describe one cyclostome, Favosipora purpurea sp. nov., which represents the first record of this genus in the Atlantic Ocean, and one cheilostome, Rhynchozoon papuliferum sp. nov. In addition, one species, Beania maxilladentata, is recorded for the first time outside of Rio de Janeiro, Brazil. Six other species previously recorded in Madeira are redescribed to provide new data and SEM images.