The number of plant species regarded as non-mycorrhizal increases at higher latitudes, and several plant species in the High-Arctic Archipelago Svalbard have been reported as non-mycorrhizal. We used the rRNA ITS2 and 18S gene markers to survey which fungi, as well as other micro-eukaryotes, were associated with roots of 31 arctic plant species not usually regarded as mycorrhizal in Svalbard. We assessed to what degree the root-associated fungi showed any host preference and whether the phylogeny of the plant hosts may mirror the composition of root-associated fungi. Fungal communities were largely structured according to host plant identity and to a less extent by environmental factors. We observed a positive relationship between the phylogenetic distance of host plants and the distance of fungal community composition between samples, indicating that the evolutionary history of the host plants plays a major role for which fungi colonize the plant roots. In contrast to the ITS2 marker, the 18S rRNA gene marker showed that chytrid fungi were prevalently associated with plant roots, together with a wide spectrum of amoeba-like protists and nematodes. Our study confirms that arbuscular mycorrhizal (AM) fungi are present also in arctic environments in low abundance.