Bioassay-guided fractionation of the antimalarial-active CHCl3 extract of the dried stem of Nauclea orientalis (L.) L. (Rubiaceae) has resulted in the isolation of two novel tetrahydro-beta-carboline monoterpene alkaloid glucosides, naucleaorine (= (16alpha,17beta)-3,14:15,20-tetradehydro-16-ethenyl-17-(beta-D-glucopyranosyloxy)-19alpha-methoxyoxayohimban-21-one; 1) and epimethoxynaucleaorine (2), as well as the known compounds, strictosidine lactam (= (15beta,16alpha,17beta)-19,20-didehydro-16-ethenyl-17-(beta-D-glucopyranosyloxy)oxayohimban-21-one; 3), 3,4,5-trimethoxyphenol (4), 3alpha-hydroxyurs-12-en-28-oic acid methyl ester (5), 3alpha,23-dihydroxyurs-12-en-28-oic acid (6), 3alpha,19alpha,23-trihydroxyurs-12-en-28-oic acid methyl ester (7), and oleanolic acid (8). Compounds 1, 2, 6, and 8 showed moderate in vitro activities against Plasmodium falciparum. Their structures and configurations were elucidated by spectroscopic methods including 1D- and 2D-NMR analyses.