The hybrid pigeonpea technology, the first of its kind in the legumes, has shown potential for a breakthrough in yield. For understanding the molecular basis of cytoplasmic male-sterility (CMS), we have used Roche/454 FLX next generation sequencing platform to sequence mitochondrial genomes of four pigeonpea lines (male-sterile ICPA2039, maintainer ICPB2039, hybrid ICPH2433 and wild relative ICPW29). A total of 545.7 kb assembled in a circular molecule of mitochondrial genome of ICPA2039. We estimated the pigeonpea genome size, based on K-mer statistics, to be 570.9 kb, suggesting that the assembly captures 95.5% of the mitochondrial genome in the genome assembly. Analysis of sequence data for GC content indicated a 44.7% GC distribution in mitochondrial genome. Genome analysis predicted 51 genes, including 34 protein-coding, 14 tRNA, 3 rRNA genes. The refined assembly of ICPA2039 was used as a reference to detect the sequence level differences with other three lines. A total of 22 rearrangements and 17 no-coverage regions were detected in ICPB2039 on comparison with ICPA2039. While comparing ICPA2039 with its wild progenitor i.e. ICPW29, 9 re-arrangements and 12 no-coverage regions were identified. Overall, the results represent important steps towards elucidation of the genetic factors responsible for cytoplasmic male-sterility in pigeonpea, which will facilitate improvement of this crop of resource-poor farmers in the semi-arid tropics.