A three-gene data set was generated to explore species diversity and delimitations within the stalked puffballs (Tulostoma, Agaricales) in Europe. Data on species from other parts of the world were included for comparison of species concepts and distribution ranges. Sequence data from 26 type specimens are included. The phylogenetic analyses support Tulostoma as monophyletic. Eleven major clades, 37 minor clades, and 20 single branches were recovered and found to correspond to 30 described species and 27 species without scientific names. Five species are here described as new to science: Tulostoma calcareum, T. calongei, T. eckbladii, T. grandisporum, and T. pannonicum. In total we report 26 described, and 19 undescribed, species from Europe. An epitype for T. fimbriatum with ITS sequence data is selected to fix the name. The recovered tree topology was not in congruence with the current infrageneric classification of Tulostoma, suggesting that many of the morphological characters used for segregation of taxa are plesiomorphic or homoplasious. Spore ornamentation and hyphal structure of the peridium are found to be reliable characters for delimitation of species. The majority of the species occur in the dry, arid areas of southern and east central Europe but a few are shown to be restricted to humid temperate regions in the North. The study confirms that species with smooth or sub-smooth spores are restricted to dry and arid habitats whereas species with more strongly ornamented spores occur in humid habitats. Areas with steppe vegetation in Hungary and Spain are here identified as hot spots for Tulostoma species diversity.