The Gray's sea fan, Paramuricea grayi (Johnson, 1861), typically inhabits deep littoral and circalittoral habitats of the eastern temperate and tropical Atlantic Ocean. Along the Iberian Peninsula, where P. grayi is a dominant constituent of circalittoral coral gardens, two segregating lineages (yellow and purple morphotypes) were recently identified using single-copy nuclear orthologues. The mitochondrial genomes of 9 P. grayi individuals covering both color morphotypes were assembled from RNA-seq data, using samples collected at three sites in southern (Sagres and Tavira) and western (Cape Espichel) Portugal. The complete circular mitogenome is 18,668 bp in length, has an A + T-rich base composition (62.5%) and contains the 17 genes typically found in Octocorallia: 14 protein-coding genes (atp6, atp8, cob, cox1-3, mt-mutS, nad1-6, and nad4L), the small and large subunit rRNAs (rns and rnl), and one transfer RNA (trnM). The mitogenomes were nearly identical for all specimens, though we identified a noteworthy polymorphism (two SNPs 9 bp apart) in the mt-mutS of one purple individual that is shared with the sister species P. clavata. The mitogenomes of the two species have a pairwise sequence identity of 99.0%, with nad6 and mt-mutS having the highest rates of non-synonymous substitutions.