Nine new alkaloids, eugeniinalines A-H (1-8) and (+)-eburnamenine N-oxide (9), comprising one quinoline, six indole, and two isogranatanine alkaloids, were isolated from the stem-bark extract of the Malayan Leuconotis eugeniifolia. The structures and absolute configurations of these alkaloids were established based on the analysis of the spectroscopic data, GIAO NMR calculations, DP4+ probability analysis, TDDFT-ECD method, and X-ray diffraction analysis. Eugeniinaline A (1) represents a new pentacyclic quinoline alkaloid with a 6/6/5/6/7 ring system. Eugeniinaline G (7) and its seco-derivative, eugeniinaline H (8), were the first isogranatanine alkaloids isolated as natural products. The known alkaloids leucolusine (10) and melokhanine A (11) were found to be the same compound, based on comparison of the spectroscopic data of both compounds, with the absolute configuration of (7R, 20R, 21S). Eugeniinalines A and G (1 and 7) showed cytotoxic activity against the HT-29 cancer cell line with IC50 values of 7.1 and 7.2 μM, respectively.