Russula albonigra is considered a well-known species, morphologically delimited by the context of the basidiomata blackening without intermediate reddening, and the menthol-cooling taste of the lamellae. It is supposed to have a broad ecological range and a large distribution area. A thorough molecular analysis based on four nuclear markers (ITS, LSU, RPB2 and TEF1-alpha) shows this traditional concept of R. albonigra s. lat. represents a species complex consisting of at least five European, three North American, and one Chinese species. Morphological study shows traditional characters used to delimit R. albonigra are not always reliable. Therefore, a new delimitation of the R. albonigra complex is proposed and a key to the described European species of R. subgen. Compactae is presented. A lectotype and an epitype are designated for R. albonigra and three new European species are described: R. ambusta, R. nigrifacta, and R. ustulata. Different thresholds of UNITE species hypotheses were tested against the taxonomic data. The distance threshold of 0.5% gives a perfect match to the phylogenetically defined species within the R. albonigra complex. Publicly available sequence data can contribute to species delimitation and increase our knowledge on ecology and distribution, but the pitfalls are short and low quality sequences.