The deep biosphere is one of the least understood ecosystems on Earth. Although most microbiological studies in this system have focused on prokaryotes and neglected microeukaryotes, recent discoveries have revealed existence of fossil and active fungi in marine sediments and sub-seafloor basalts, with proposed importance for the subsurface energy cycle. However, studies of fungi in deep continental crystalline rocks are surprisingly few. Consequently, the characteristics and processes of fungi and fungus-prokaryote interactions in this vast environment remain enigmatic. Here we report the first findings of partly organically preserved and partly mineralized fungi at great depth in fractured crystalline rock (-740 m). Based on environmental parameters and mineralogy the fungi are interpreted as anaerobic. Synchrotron-based techniques and stable isotope microanalysis confirm a coupling between the fungi and sulfate reducing bacteria. The cryptoendolithic fungi have significantly weathered neighboring zeolite crystals and thus have implications for storage of toxic wastes using zeolite barriers.