The myrmecophilous carabid beetle, Paussus favieri, has a circum-Mediterranean distribution and it is completely dependent upon its host ant Pheidole pallidula during all stages of its life history. Using molecular sequence data we inferred the phylogenies of the populations of both the beetle and its ant host to determine if there are signs of co-evolution. A total of 34 P. favieri from France, Spain, Portugal, Morocco and Tunisia and 42 Ph. pallidula workers from the same countries, plus Greece and Italy, were collected and analyzed. Many mitochondrial and nuclear markers were sequenced, but only COI was evolving fast enough to infer the population-level phylogenies of the beetles and the ants. Preliminary analyses suggest that the European populations of P. favieri are derived from a single dispersal event from Africa, while several dispersal events are suggested for Ph. pallidula. We found the topologies of host and parasite trees to be generally congruent, as would be expected if the host and parasite have had a history of co-evolution or co-divergence.