A phylogenetic analysis of 40 species (22 genera) of the Palaearctic millipede family Julidae was made based on partial sequences of the mitochondrial 16S rRNA (16S) gene and the nuclear 28S rRNA (28S) gene, respectively. The two data sets (16S rDNA and 28S rDNA) were analysed individually and in combination using direct optimization as implemented in POY. The 16S rDNA and the 28S rDNA sequences vary from 410 to 449 bp and from 467 to 525 bp in length, respectively. All searches were performed under six different gap opening costs, an extension gap cost of 1, and a substitution cost of 2. Incongruence length difference values were used to select the preferred tree. The order Julida was recovered as monophyletic under all weight sets. The family Julidae was recovered as monophyletic except under one weight set where the genus Nepalmatoiulus is sister to all other Julida. Within Julidae, a clade of Paectophyllini + Calyptophyllini is sister to all others on the preferred tree but this relationship is not robust. A hitherto unrecognized clade of (South) east Asian genera (Anaulaciulus and Nepalmatoiulus) was recovered under five weight sets. Another "new" robust clade (Oncoiulini + Schizophyllini) is congruent with a hitherto unrecognized complex morphological character. Further clades recovered within the Julidae partly conflict with the accepted classification, which is only to a limited extent based on phylogenetic arguments.