A worldwide survey of Wallemia occurring in house dust and indoor air was conducted. The isolated strains were identified as W. sebi and W. muriae. Previous studies suggested that the W. sebi phylogenetic clade contained cryptic species but conclusive evidence was lacking because only the internal transcribed spacer (ITS) marker was analyzed. The ITS and four protein-coding genes (MCM7, RPB1, RPB2, and TSR1) were sequenced for 85 isolates. Based on an initial neighbor joining analysis of the concatenated genes, W. muriae remained monophyletic but four clades were found in W. sebi, which we designated as W. sebi clades 1, 2, 3, and 4. We hypothesized that these clades represent distinct phylogenetic species within the Wallemia sebi species complex (WSSC). We then conducted multiple phylogenetic analyses and demonstrated genealogical concordance, which supports the existence of four phylogenetic species within the WSSC. Geographically, W. muriae was only found in Europe, W. sebi clade 3 was only found in Canada, W. sebi clade 4 was found in subtropical regions, while W. sebi clade 1 and 2 were found worldwide. Haplotype analysis showed that W. sebi clades 1 and 2 had multiple haplotypes while W. sebi clades 3 and 4 had one haplotype and may have been under sampled. We describe W. sebi clades 2, 3, and 4 as new species in a companion study.