Paraphlomis is a genus of Lamiaceae with about 30 species distributed mainly in subtropical China. In this study, we carried out the first molecular phylogenetic analyses to elucidate the relationships within the genus based on two nuclear and four plastid DNA regions. Our results, which recovered a species of Matsumurella within Paraphlomis, indicate that the genus is not monophyletic. The two sections and most of the series previously described within the genus are also shown to be polyphyletic. Combining with morphological evidence, our study indicates that nutlet morphology rather than calyx morphology is of phylogenetic value for the infrageneric classification of Paraphlomis. Moreover, P. jiangyongensis, a new species from southern China, is here described, and P. coronata, formerly treated as a variety of P. javanica, is here resurrected as a distinct species within the genus.