Ectomycorrhizae are formed by mutualistic interactions between fungi and the roots of woody plants. During symbiosis the two organisms exchange carbon and nutrients in a specific tissue that is formed at the contact between a compatible fungus and plant. There is considerable variation in the degree of host specificity among species and strains of ectomycorrhizal fungi. In this study, we have for the first time shown that this variation is associated with quantitative differences in gene expression, and with divergence in nucleotide sequences of symbiosis-regulated genes. Gene expression and sequence evolution were compared in different strains of the ectomycorrhizal fungus Paxillus involutus; the strains included Nau, which is not compatible with birch and poplar, and the two compatible strains Maj and ATCC200175. On a genomic level, Nau and Maj were very similar. The sequence identity was 98.9% in the 16 loci analysed, and only three out of 1075 genes analysed by microarray-based hybridizations had signals indicating differences in gene copy numbers. In contrast, 66 out of the 1075 genes were differentially expressed in Maj compared to Nau after contact with birch roots. Thirty-seven of these symbiosis-regulated genes were also differentially expressed in the ATCC strain. Comparative analysis of DNA sequences of the symbiosis-regulated genes in different strains showed that two of them have evolved at an enhanced rate in Nau. The sequence divergence can be explained by a decreased selection pressure, which in turn is determined by lower functional constraints on these proteins in Nau as compared to the compatible strains.