The higher level phylogeny of fungi has been addressed in previous studies, but for those analyses, either taxon sampling or gene sampling was low, or some basal lineages important for the inference of basidiomycete phylogeny were lacking. Here, a phylogenomic analysis based on highly conserved genes and including the enigmatic species Bartheletia paradoxa from Ginkgo biloba is presented. While phylogenetic analyses including also less conserved parts of core eukaryotic genes yielded a basal position for the extremophile genus Wallemia with low support, an exclusion of highly variable parts of these genes suggested Bartheletia paradoxa as the most basal member of the Agaricomycotina, but again with low support. Network analyses suggest a network-like evolution at the base of the Basidiomycota, supported by phylogenies based on single genes and gene clusters with shared topology. When further removing noise by removing poorly resolving genes, strong but not maximum support was obtained for Bartheletia paradoxa being the sister lineage to all other Agaricomycotina. We speculate that the lack of support for the early splits in Agaricomycotina and Basidiomycota can probably be explained by rapid radiation, linked to major evolutionary developments, such as, in the case of Basidiomycota, the advent of basidia in the last common ancestor.