The cytotoxicity of 39 compounds, including eighteen flavonoids (flavanones, 1–10; flavones, 11–17; flavanol, 18), sixteen phenolic acid derivatives (aromatic acids, 19–24; aldehyde, 25; esters, 26–34) and five glycerides (35–39), isolated from Mexican propolis, were evaluated against a panel of six different cancer cell lines; murine colon 26-L5 carcinoma, murine B16-BL6 melanoma, murine Lewis lung carcinoma, human lung A549 adenocarcinoma, human cervix HeLa adenocarcinoma and human HT-1080 fibrosarcoma. A phenylpropanoid-substituted flavanol, (2R,3S)-8-[4-phenylprop-2-en-1-one]-4’,7-dihydroxy-3’,5-dimethoxyflavan-3-ol (18), showed the most potent cytotoxicity against A549 cells (IC50, 6.2 μM) and HT-1080 cells (IC50, 3.9 μM), stronger than those of the clinically used anticancer drug, 5-fluorouracil (IC50, 7.5 μM and 5.4 μM, respectively). Based on the observed results, the structure–activity relationships are discussed.