Plant-derived nanovesicles (PDNVs) have been proposed as a major mechanism for the inter-kingdom interaction and communication, but the effector components enclosed in the vesicles and the mechanisms involved are largely unknown. The plant Artemisia annua is known as an anti-malaria agent that also exhibits a wide range of biological activities including the immunoregulatory and anti-tumor properties with the mechanisms to be further addressed. Here, we isolated and purified the exosome-like particles from A. annua, which were characterized by nano-scaled and membrane-bound shape and hence termed artemisia-derived nanovesicles (ADNVs). Remarkably, the vesicles demonstrated to inhibit tumor growth and boost anti-tumor immunity in a mouse model of lung cancer, primarily through remolding the tumor microenvironment and reprogramming tumor-associated macrophages (TAMs). We identified plant-derived mitochondrial DNA (mtDNA), upon internalized into TAMs via the vesicles, as a major effector molecule to induce the cGAS-STING pathway driving the shift of pro-tumor macrophages to anti-tumor phenotype. Furthermore, our data showed that administration of ADNVs greatly improved the efficacy of PD-L1 inhibitor, a prototypic immune checkpoint inhibitor, in tumor-bearing mice. Together, the present study, for the first time, to our knowledge, unravels an inter-kingdom interaction wherein the medical plant-derived mtDNA, via the nanovesicles, induces the immunostimulatory signaling in mammalian immune cells for resetting anti-tumor immunity and promoting tumor eradication.