Thirty-five diverse polyphenols, belonging to seven structure classes, were isolated from Garcinia gracilis, a medicinal and edible plant sampled from Laos. The structures of nine new compounds, gargarcilones A-I (1-3, 5-7, 10, 12, and 17), were established using spectroscopic, X-ray diffraction, and experimental and calculated ECD methods. Additionally, we revised the stereochemical assignment of cochinchinoxanthone and cochinchinoxanthone C. The compounds were evaluated for antiproliferative activity against five human tumor cell lines (HL-60, A549, SMMC-7721, MDA-MB-231, and SW480). Compounds 1-4, 7, and 8 exhibited cytotoxic activity with IC50 values of 0.5-8.9 μM. Compound 3 significantly induced apoptosis in SMMC-7721 cells.