Lace bugs (Tingidae) are a family of phytophagous heteropterans, some of which are important agricultural and forestry pests. They currently comprise around 2500 species distributed worldwide, for which only one mitochondrial genome has been described so far. We sequenced the complete mitochondrial genome and the nuclear ribosomal gene segment of the avocado lace bug Pseudacysta perseae using a genome skimming approach on an Illumina Hiseq 2000 platform. Fifty-four additional heteropteran mitogenomes, including the one of the sycamore lace bug Corythucha ciliata, were retrieved to allow for comparisons and phylogenetic analyses. P. perseae mitochondrial genome was determined to be 15,850 bp long, and presented the typical organisation of insect mitogenomes. The phylogenetic analysis placed P. perseae as a sister to C. ciliata but did not confirm the monophyly of Miroidae including Tingidae. Our results contradicted widely accepted phylogenetic hypothesis, which highlights the limits of analyses based on mitochondrial data only. Shotgun sequencing approaches should provide substantial improvements in harmonizing mitochondrial and nuclear databases.