Background: This work aimed at characterizing 12 isolates of the genus Tuber including Tuber melanosporum (11 isolates) and Tuber brumale (one isolate). This was done using internal transcribed spacer (ITS) sequences, confirming their origin. Results: Analysis of their mating type revealed that both MAT1-1 and MAT1-2 exist within these isolates (with 3 and 8 of each, respectively). We observed that each of these cultures was consistently associated with one bacterium that was intimately linked to fungal growth. These bacterial associates failed to grow in the absence of fungus. We extracted DNA from bacterial colonies in the margin of mycelium and sequenced a nearly complete 16S rDNA gene and a partial ITS fragment. We found they all belonged to the genus Rhodopseudomonas, fitting within different phylogenetic clusters. No relationships were evidenced between bacterial and fungal strains or mating types. Rhodopseudomonas being a sister genus to Bradyrhizobium, we tested the nodulation ability of these bacteria on a promiscuously nodulating legume (Acacia mangium), without success. We failed to identify any nifH genes among these isolates, using two different sets of primers. Conclusions: While the mechanisms of interaction between Tuber and Rhodopseudomonas remain to be elucidated, their interdependency for in vitro growth seems a novel feature of this fungus.