A new collection of several Red Sea sponges was investigated for the discovery of potential breast cancer migration inhibitors. Extracts of the Verongid sponges Pseudoceratina arabica and Suberea mollis were selected. Bioassay-directed fractionation of both sponges, using the wound-healing assay, resulted into the isolation of several new and known brominated alkaloids. Active fractions of the sponge Pseudoceratina arabica afforded five new alkaloids, ceratinines A-E (2-6), together with the known alkaloids moloka'iamine (1), hydroxymoloka'iamine (7) and moloka'iakitamide (8). The active fraction of the sponge Suberea mollis afforded the three known alkaloids subereamolline A (9), aerothionin (10) and homoaerothionin (11). Ceratinine B (3) possesses an unprecedented 5,7-dibrominated dihydroindole moiety with an epoxy ring on the side chain of a fully substituted aromatic moiety. Ceratinines D (5) and E (6) possess a terminal formamide moiety at the ethylamine side chain. Subereamolline A (9) potently inhibited the migration and invasion of the highly metastatic human breast cancer cells MDA-MB-231 at the nanomolar doses. Subereamolline A and related brominated alkaloids are novel scaffolds appropriate for further future use for the control of metastatic breast cancer.