The recent developments in high-throughput DNA sequencing allowed major advances in organelle genomics. Assembly of mitochondrial genomes (hereafter mitogenomes) in higher plants however remains a challenge due to their large size and the presence of plastid-derived regions and repetitive sequences. In this study, we reconstructed the first mitogenome of Oleaceae using a herbarium specimen of the extinct genus Hesperelaea collected in 1875. Paired-end reads produced with the HiSeq technology (shotgun) in a previous study were re-used. With an approach combining reference-guided and de novo assembly, we obtained a circular molecule of 658,522bp with a mean coverage depth of 35×. We found one large repeat (ca. 8kb) and annotated 46 protein-coding genes, 3 rRNA genes and 19 tRNA genes. A phylogeny of Lamiales mitogenomes confirms Oleaceae as sister to a group comprising Lamiaceae, Phyrmaceae and Gesneriaceae. The Hesperelaea mitogenome has lower rates of synonymous and non-synonymous substitution compared to Nicotiana tabacum than other available mitogenomes of Lamiales. To conclude, we show that mitogenome reconstruction in higher plants is possible with shotgun data, even from poorly preserved DNA extracted from old specimens. This approach offers new perspectives to reconstruct plant phylogenies from mitochondrial markers, and to develop functional mitogenomics in Oleaceae.