The ethanol extract of Pseudoalteromonas strain J010, isolated from the surface of the crustose coralline alga Neogoniolithon fosliei, yielded thirteen natural products. These included a new bromopyrrole, 4′-((3,4,5-tribromo- 1H-pyrrol-2-yl)methyl)phenol (1) and five new korormicins G-K (2-6). Also isolated was the known inducer of coral larval metamorphosis, tetrabromopyrrole (TBP), five known korormicins (A-E, previously named 1, 1a-c and 3) and bromoalterochromide A (BAC-A). Structures of the new compounds were elucidated through interpretation of spectra obtained after extensive NMR and MS investigations and comparison with literature values. The antibacterial, antifungal and antiprotozoal potential of 1-6, TBP and BAC-A was assessed. Compounds 1-6 showed antibacterial activity while BAC-A exhibited antiprotozoal properties against Tetrahymena pyriformis. TBP was found to have broad-spectrum activity against all bacteria, the protozoan and the fungus Candida albicans. © 2014 by the authors licensee MDPI.