Accurate assessment of tumour heterogeneity is an important issue that influences prognosis and therapeutic decision in molecular pathology. Due to the shortage of protective histones and a limited DNA repair capacity, the mitochondrial (mt)-genome undergoes high variability during tumour development. Therefore, screening of mt-genome represents a useful molecular tool for assessing precise cell lineages and tracking tumour history. Here, we describe a highly specific and robust multiplex PCR-based ultra-deep sequencing technology for analysis of the whole mt-genome (wmt-seq) on low quality-DNA from formalin-fixed paraffin-embedded tissues. As a proof of concept, we applied the wmt-seq technology to characterize the clonal relationship of non-small cell lung cancer (NSCLC) specimens with multiple lesions (N = 43) that show either different histological subtypes (group I) or pulmonary adenosquamous carcinoma as striking examples of a mixed-histology tumour (group II). The application of wmt-seq demonstrated that most samples bear common mt-mutations in each lesion of an individual patient, indicating a single cell progeny and clonal relationship. Hereby we show the monoclonal origin of histologically heterogeneous NSCLC and demonstrate the evolutionary relation of NSCLC cases carrying heteroplasmic mt-variants.