Palytoxin (PTX), one of the most potent and chemically complex marine toxins, is predominantly found in zoanthid corals and sporadically in dinoflagellates. Its biosynthesis and metabolic pathways are largely unknown. However, the widespread occurrence of the toxin in phylogenetically distinct marine organisms is consistent with its production by microorganisms and subsequent accumulation in the food chain. To investigate a possible microbial origin, bacteria from two zoanthid corals (Palythoa caribaeorum, Zoanthus pulchellus) and one sponge (Neofibularia nolitangere) were isolated. More than 250 bacteria were screened for hemolysis using a newly developed PTX-screening assay of which 7% showed PTX-like hemolytic activity. 16S rRNA gene sequencing revealed that these bacterial isolates belonged to strains of Bacillus cereus group (n = 11) as well as the genera Brevibacterium (n = 4) and Acinetobacter (n = 2). The results indicate the presence of Na+/K+-ATPase toxins and possibly PTX in hemolytic bacteria from P. caribaeorum.