A Red Sea specimen of the marine sponge Hyrtios erectus was found to contain three new alkaloids, hyrtioerectines A-C (1-3). Hyrtioerectine A (1) possesses the carbon bond-linked moieties 6-hydroxy beta-carboline and 6-hydroxyindole. The structure elucidation of 1-3 was based on intensive study of their spectral data including 1D (1H and 13C) and 2D (1H-1H COSY, HOHAHA, NOESY, ROESY, HMQC, and HMBC) NMR, together with high-resolution mass spectra. Hyrtioerectines A-C were moderately cytotoxic.