Pennatulaceans are an important component of benthic marine communities usually related to soft bottoms. Despite their important ecological role, as yet little is known about their origin and divergence time. The first attempts to establish phylogenetic relationships among genera date from the early 20th century, when only morphological characters were available. In the last decade, phylogenetic analyses based on mitochondrial DNA sequences from a selected number of species have proposed a different hypothetical ancestor for this group, but their intergeneric relationships remain obscure. The present study is based on a combination of mitochondrial and nuclear markers (mtMutS, Cox1 and 28S rDNA), adding new molecular information about the phylogenetic relationships among the pennatulacean genera, including 38 new sequences belonging to 13 different species. Some of the phylogenetic relationships inferred in the present study question the current classification of sea pens based on morphology (at different taxonomic levels), clearly indicating that the two main groups Sessiliflorae and Subselliflorae, some of their main families (e.g. Pennatulidae, Umbellulidae, Virgulariidae) and some genera (e.g. Umbellula, Veretillum) are non-monophyletic. In addition, the veretillids, traditionally considered the most primitive pennatulaceans, are not shown as the earliest-diverging taxon. Moreover, an analysis of divergence time performed here suggested that the origin of the pennatulaceans dates from the Lower Cretaceous (Berriasian, ~144 Ma), in agreement with their sparsely known fossil record, while the initial divergence of most extant genera occurred in the Oligocene and Miocene times.