Molecular analyses of the ecologically important gorgonian octocoral genus Leptogorgia are scant and mostly deal with few species from restricted geographical regions. Here we explore the phylogenetic relationships and the evolutionary history of Leptogorgia using the complete mitochondrial genomes of six Leptogorgia species from different localities in the Atlantic, Mediterranean and eastern Pacific as well as four other genera of Gorgoniidae and Plexauridae. Our mitogenomic analyses showed high inter-specific diversity, variable nucleotide substitution rates and, for some species, novel genomic features such as ORFs of unknown function. The phylogenetic analyses using complete mitogenomes and an extended mtMutS dataset recovered Leptogorgia as polyphyletic, and the species considered in the analyses were split into two defined groups corresponding to different geographic regions, namely the eastern Pacific and the Atlantic-Mediterranean. Our phylogenetic analysis based on mtMutS also showed a clear separation between the eastern Atlantic and South African Leptogorgia, suggesting the need of a taxonomic revision for these forms. A time-calibrated phylogeny showed that the separation of eastern Pacific and western Atlantic species started ca. 20 Mya and suggested a recent divergence for eastern Pacific species and for L. sarmentosa-L. capverdensis. Our results also revealed high inter-specific diversity among eastern Atlantic and South African species, highlighting a potential role of the geographical diversification processes and geological events occurring during the last 30 Ma in the Atlantic on the evolutionary history of these organisms.