The Australian genus Reddellomyces comprises several closely related symbiotic ascomycetes with chambered gleba (solid ptychothecium), ornamented ascospores and cylindrical paraphyses that are sometimes difficult to identify based on morphological aspects. Several Reddellomyces species are spread with their Australian host plants (Eucalyptus and Acacia) worldwide including Mediterranean areas. Specimens of an unusual truffle were collected from Acacia saligna stands in Tunisian semi-arid lands and eucalypt forest of Antalya (Turkey) dominated by E. camaldulensis Dehnh. and E. grandis W. Hill. Based on morphological features, these fungi are affiliated to Reddellomyces genus, differing from other species of the genus mainly based on ascospore size. Further analysis based on nuclear rDNA LSU and ITS and digital RFLP of the ITS sequenced amplicons with selected restriction endonucleases showed the unique identity of Tunisian specimens within the genus Reddellomyces. Our results showed also that at least six Reddellomyces species are present including two unnamed species restricted to Australia.