Two new quinoline alkaloids, aaptolines A and B, were isolated from the marine sponge Aaptos aaptos. Their structures were determined by HR-ESI-MS data, NMR analysis, and X-ray crystallography. Structurally, aaptoline A is characterized as having a quinoline skeleton fused with a 1,4-dioxane motif at the C(7)-C(8) position, whereas aaptoline B possessed an intriguing 1H-pyrrolo[2,3-g]quinoline moiety. The cytotoxic assay of these compounds showed no cytotoxicity towards HepG2, A549, and PC9 cancer cell lines and had IC50 values greater than 20 mu m.