Bursaphelenchus xylophilus is the causal agent of pine wilt disease and a worldwide pest with high economic impact. Since its first diagnosis in Portugal in 1999, it has been subjected to quarantine measures with impact on forest health and ecosystem stability, significantly affecting international trade of wood products. The disease was detected in the north and centre of continental Portugal and, since 2008, the whole country has been considered an affected area. Recently, it was detected in Madeira Island. In order to avoid new outbreaks, it has become of major importance to understand the patterns of spread, introduction points and to characterize the new populations from continental Portugal and Madeira Island. Mitochondrial cytochrome b (cytb) and parasitic cellulase gene sequences were used to evaluate the genetic relationships among isolates that could indicate possible origins of the new outbreaks. Portuguese isolates were compared with isolates from USA, China, Japan and South Korea, in order to investigate possible infection pathways and disease spread patterns in Portugal. Phylogenetic trees based on both genes show that Portuguese isolates group with Asian isolates. Isolates from USA are in a separate position in both gene trees. However, the phylogenetic tree based on the cellulase gene sequences shows higher differentiation among Portuguese isolates than that of cytb. These results agree with those previously obtained using inter-simple sequence repeats (ISSR). This was the first study to use cytb and cellulase genes to characterize pinewood nematode (PWN) populations. This study suggests that cellulase is a better marker than cytb to study genetic diversity in B. xylophilus.