Of the more than 400 indigenous orchid species in Western Australia, Cryptostylis ovata is the only species that retains its leaves all year round. It exists as a terrestrial herb and occasionally as an epiphyte in forested areas. Like all terrestrial orchids, C. ovata plants associate with mycorrhizal fungi, but their identities have not previously been investigated. Fungi were isolated from pelotons in rhizomes collected from three southern and two northern populations of C. ovata on six occasions over two years. Phylogenetic analysis of ITS sequences temporally and spatially revealed that all the fungal isolates were of Tulasnella species of four distinct groups. One Tulasnella group was present only in the three southern orchid populations, and it closely resembled T. prima isolates previously described from Chiloglottis sp. orchids from eastern Australia. Isolates collected from plants in the two northern populations were of three undescribed Tulasnella groups. Analysis of intra-group diversity using inter-simple sequence repeat markers revealed that plants were usually colonised by a single genotype of Tulasnella at each sampling period, and this genotype usually, but not always, persisted with the host plant over both years tested.