The mitochondrial (mt) genome differs from the nuclear genome by its high copy number, small size, intronless genomic structure, different mode of replication, exposure to oxygen radicals and increased DNA damage. While it is well-established that tumor-specific mt variants and mutations are present in many cancers, little is known about changes within the mt genome during tumor progression in general and during initiation and progression of neuroblastoma (NB) in particular. Analysis of mt sequences extracted from whole exome sequencing data of corresponding normal tissue, primary (diagnostic) tumors and relapsed tumors of 16 NB patients that we previously had investigated for nuclear mutations, revealed that most NB harbor tumor-specific mitochondrial variants. In relapsed tumors, the status of mt variants changed, as shown by increased number and spatio-temporal differences of tumor-specific variants, and by a concomitant decrease of germline variants. The spectrum of mutations at initial disease was consistent with replication-induced but not with reactive oxygen species-induced DNA damage and, in contrast to the nuclear genome, did not change at relapse, suggesting different mutating mechanisms. As mt variants are present in most NB patients, change during relapse and have a higher copy number compared to nuclear variants, they represent a promising new source of biomarkers for monitoring and phylogenetic analysis of NB.