Cytotoxicity screenings have identified Plectranthus plants as potential sources of antitumor lead compounds. In this work, several extracts from Plectranthus madagascariensis were prepared using different solvents (acetone, methanol, and supercritical CO2) and extraction techniques (maceration, ultrasound-assisted, and supercritical fluid extraction), and their chemical composition was detailed using high-performance liquid chromatography with a diode array detector. The cytotoxic activity of the major compounds identified, namely, rosmarinic acid (1) and abietane diterpenes 7α,6β-dihydroxyroyleanone (2), 7α-formyloxy-6β-hydroxyroyleanone (3), 7α-acetoxy-6β-hydroxyroyleanone (4), and coleon U (5), was evaluated in a battery of human cancer cell lines, including breast (MDA-MB-231, MCF-7), colon (HCT116), and lung (NCI-H460, NCI-H460/R) cancer, and also in healthy lung (MCR-5) cells. Royleanone (3) was isolated for the first time from P. madagascariensis, and its full spectroscopic characterization (proton and carbon nuclear magnetic resonance) was accomplished. A high selectivity for lung cancer cells was observed for royleanones (2, 4) with selectivity indexes of 4.3 and 3.2, respectively. The observed results combined with literature data allowed the establishment of important structure-activity relationships for substituted royleanone abietanes, such as the requirement for an electron-donating group at positions 6 and/or 7 in the abietane skeleton, and an improved cytotoxic effect for substituents with log P values between 2 and 5.