This paper provides the first DNA sequences and phylogenetic insight into the Central Asian genus Eodorcadion. We used four molecular markers (COI, CAD, ITS2, and Histone 3) and investigated COI genetic distances to verify phylogenetic position of closely related taxa endemic to Mongolia of the ‘Eodorcadion intermedium species-group’. Histone3 data are presented for the first time for Cerambycidae species. We also designed new PCR primers for better amplification of the Cerambycidae COI barcode region. Morphology of all targeted taxa was examined by means of scanning electron microscopy. Our study showed that while there were very few nucleotide differences among COI sequences of three closely related taxa, such that they shared one haplotype, two of them were grouped separately in the all-data tree, and all three were morphologically distinguishable. Conversely, there was a clear barcode gap between E. intermedium intermedium and all the remaining taxa, including E. intermedium kozlovi. Based on the phylogeny, they belong to two different species-groups; thus, E. kozlovi is herein restored to specific rank. Using Bayesian analysis, we contrasted the COI-based tree with the one supported by nuclear data and showed that COI-only data are not sufficient to resolve the phylogeny of the recently derived flightless groups such as Dorcadionini. We conclude that the Eodorcadion intermedium species-group is a polyphyletic species assemblage, established based on the pattern of the elytral stripes, which may be a case of parallel evolution driven by ecological adaptation.