Many tumors including prostate cancer are maintained by cancer stem cells (CSCs), which might cause tumor relapse if not eradicated during the course of treatment. Specific targeting or radiosensitization of CSCs bear promise to improve tumor curability by synergistic effects in combination with radiotherapy. Carbon nanotubes (CNTs) can be used as promising drug delivery systems for anticancer drugs such as the flavonoid catechin. Catechin is an extensively studied active ingredient of the different plants, including green tea, and it is widely recognized as co-adjuvant in cancer therapy. Here we describe the synthesis of biocompatible, catechin-loaded and gelatin-conjugated CNTs (Gel_CT_CNTs) with anticancer properties and demonstrate their potential for the eradication of prostate CSCs in combination with X-ray irradiation. Gel_CT_CNTs showed a significant enhancement of in vitro anticancer activity as compared to catechin alone. Moreover, treatment of prostate cancer cells with Gel_CT_CNT nanohybrids inhibited the tumorigenic cell population defined by a high aldehyde dehydrogenase (ALDH) activity. A combination of X-ray irradiation and treatment with Gel_CT_CNTs caused a decrease in the protein level of stem cell-related transcription factors and regulators including Nanog, Oct4 and β-catenin and led to an increase of cancer cell radiosensitivity as demonstrated by clonogenic and spherogenic cell survival assays. Taken together, our results suggest that a combination of irradiation and Gel_CT_CNTs can be potentially used for the radiosensitization and eradication of prostate CSC populations.