Alteration of organic remains during the transition from the bio- to lithosphere is affected strongly by biotic processes of microbes influencing the potential of dead matter to become fossilized or vanish ultimately. If fossilized, bones, cartilage, and tooth dentine often display traces of bioerosion caused by destructive microbes. The causal agents, however, usually remain ambiguous. Here we present a new type of tissue alteration in fossil deep-sea shark teeth with in situ preservation of the responsible organisms embedded in a delicate filmy substance identified as extrapolymeric matter. The invading microorganisms are arranged in nest- or chain-like patterns between fluorapatite bundles of the superficial enameloid. Chemical analysis of the bacteriomorph structures indicates replacement by a phyllosilicate, which enabled in situ preservation. Our results imply that bacteria invaded the hypermineralized tissue for harvesting intra-crystalline bound organic matter, which provided nutrient supply in a nutrient depleted deep-marine environment they inhabited. We document here for the first time in situ bacteria preservation in tooth enameloid, one of the hardest mineralized tissues developed by animals. This unambiguously verifies that microbes also colonize highly mineralized dental capping tissues with only minor organic content when nutrients are scarce as in deep-marine environments.