Natural polyphenols are secondary metabolites of plants involved in defense against different types of stress. Extracts containing these compounds have been used for thousands of years in traditional eastern medicine. Polyphenols act on multiple targets in pathways and mechanisms related to carcinogenesis, tumor cell proliferation and death, inflammation, metastatic spread, angiogenesis, or drug and radiation resistance. Nevertheless, reported effects claimed for polyphenols are controversial, since correlations between in vitro effects and in vivo evidence are poorly established. The main discrepancy between health claims versus clinical observations is the frequent use of nonphysiologically relevant concentrations of these compounds and their metabolites in efficacy and mechanistic studies. The present review will discuss how in vivo administration correlates with polyphenol metabolism, toxicity, and bioavailability. Analysis of the general application of polyphenols in cancer therapy will be complemented by potential applications in the therapy of specific tumors, including melanoma, colorectal and lung cancers. Possible pharmaceutical formulations, structural modifications, combinations, and delivery systems aimed to increase bioavailability and/or biological effects will be discussed. Final remarks will include recommendations for future research and developments.