Corals harbor diverse and abundant prokaryotic populations. Bacterial communities residing in the coral mucus layer may be either pathogenic or symbiotic. Some species may produce antibiotics as a method of controlling populations of competing microbial species. The present study characterizes cultivable Pseudoalteromonas sp. isolated from the mucus layer of different coral species from the northern Gulf of Eilat, Red Sea, Israel. Six mucus-associated Pseudoalteromonas spp. obtained from different coral species were screened for antibacterial activity against 23 tester strains. Five of the six Pseudoalteromonas strains demonstrated extracellular antibacterial activity against Gram-positive-but not Gram-negative-tester strains. Active substances secreted into the cell-free supernatant are heat-tolerant and inhibit growth of Bacillus cereus, Staphylococcus aureus, and of ten endogenous Gram-positive marine bacteria isolated from corals. The Pseudoalteromonas spp. isolated from Red sea corals aligned in a phylogenetic tree with previously isolated Pseudoalteromonas spp. of marine origin that demonstrated antimicrobial activity. These results suggest that coral mucus-associated Pseudoalteromonas may play a protective role in the coral holobiont's defense against potential Gram-positive coral pathogens.