Phylogenetic analysis of Plasmodium parasites has indicated that their modern-day distribution is a result of a series of human-mediated dispersals involving transport between Africa, Europe, America, and Asia. A major outstanding question is the phylogenetic affinity of the malaria causing parasites Plasmodium vivax and falciparum in historic southern Europe—where it was endemic until the mid-20th century, after which it was eradicated across the region. Resolving the identity of these parasites will be critical for answering several hypotheses on the malaria dispersal. Recently, a set of slides with blood stains of malaria-affected people from the Ebro Delta (Spain), dated between 1942 and 1944, have been found in a local medical collection. We extracted DNA from three slides, two of them stained with Giemsa (on which Plasmodium parasites could still be seen under the microscope) and another one consisting of dried blood spots. We generated the data using Illumina sequencing after using several strategies aimed at increasing the Plasmodium DNA yield: depletion of the human genomic (g)DNA content through hybridization with human gDNA baits, and capture-enrichment using gDNA derived from P. falciparum. Plasmodium mitochondrial genome sequences were subsequently reconstructed from the resulting data. Phylogenetic analysis of the eradicated European P. vivax mtDNA genome indicates that the European isolate is closely related to the most common present-day American haplotype and likely entered the American continent post-Columbian contact. Furthermore, the European P. falciparum mtDNA indicates a link with current Indian strains that is in agreement with historical accounts.