Desert truffles belonging to Terfezia are well known mycorrhizal members of the mycota of the Mediterranean region and the Middle East. We aimed to test (i) whether the morphological criteria of Terfezia species regularly collected in Spain enable their separation and (ii) whether the previously hypothesized edaphic/biotic specificity of one group could be confirmed by study of a larger number of specimens. The species T. arenaria and T. claveryi can be identified unambiguously by morphological characters. We consider T. leptoderma as a distinct species while several lineages of similar spiny spored Terfezia truffles with cellular peridium were detected that have no obvious anatomical differences. Several species treated generally as synonyms of T. olbiensis have been described in this group, and because they cannot be unambiguously assigned to separate lineages we propose to consider the group as the T. olbiensis species complex. A high level of intrasporocarpic variation of the nrDNA ITS was detected in the T. olbiensis species complex, especially in one of its lineages. We detected no exclusive specificity to either plant associates or soil, except in T. leptoderma, which was associated with Quercus spp. and cistaceous plants on acidic soils. Nevertheless the clades showed a tendency either to associate with Quercus/Helianthemum/Cistus or Pinus hosts. Specimens having distinct anatomical features, reticulate spores and cellular peridium formed a separate group in the molecular phylogenetic analyses of nrDNA ITS and LSU regions; for these specimens we propose a new species, Terfezia alsheikhii sp. nov.