“Matsushimeji” identified as Tricholoma albobrunneum belonging to sect. Genuina is an edible mushroom commonly used in Japan. This species has been suggested to include another cryptic species with common morphological characteristics and identical internal transcribed spacer (ITS) sequences of nuclear ribosomal DNA (nuc rDNA). We compared T. albobrunneum specimens sampled in Japan and Denmark, including the holotype. Phylogenetic analyses of nuc rDNA ITS and intergenic spacer 1 (IGS1) regions, and tef-1a and rpb2 genes identified two phylogroups in Japanese T. albobrunneum. In addition, both Japanese phylogroups of T. albobrunneum were distinguished from European T. albobrunneum. Concatenated phylogenetic tree analysis based on these four DNA regions also distinguished two Japanese clades within T. albobrunneum. Here, we report two new species, T. matsushimeji distributed on Honshu Island under two-needle pines and T. miyama-matsushimeji on Rishiri Island under a five-needle pine from Japan.