The complete mitochondrial genome of Paragorgia papillata Li et al., 2021, a deep-sea gorgonian inhabiting at 858 m in Caroline Ridge, was obtained in this study. The length of the mitochondrial genome is 19,018 bp with 14 protein coding genes, one transfer RNA (tRNA-Met) and two ribosomal genes contained in this circular molecule. Phylogenetic analysis indicated that P. papillata and P. coralloides Bayer, 1993 were two closely related species, and a total of 26 mutational sites (four nonsynonymous mutations included) can be detected between their mitochondrial genomes. This exhibits a case that mitochondrial genomes can be applied to differentiate closely related species in soft corals. The phylogenetic tree constructed in this study showed that several families in the order Alcyonacea which P. papillata belongs to were not monophyletic, suggesting further revisions are needed for this complex clade in future studies.