The objects of cultural heritage are composed of varied materials which can be affected by diverse microbial communities. The study of these complex and heterogeneous assemblies of materials and microorganisms require an inter- and multi-disciplinary approach. Development of a strategy towards prevention, mitigation of biodeterioration and removal of microorganisms, especially fungi begins with the understanding of the materials’ fabric, assessment of causes behind the biodeterioration, and the context in which it occurs. Three aspects of biodeterioration of cultural heritage are discussed: 1) the multitude of bio-agents’ on cultural heritage materials, 2) fungal interaction with substrates, and 3) prevention and conservation of biodeteriorated artworks. The challenges of a conservators’ work in dealing with bio-degraded museum collections are discussed based on the case studies of biodeteriorated art on paper, exemplifying two types of fungal interaction with the substrate: 1) surface deposits of pigmented spores/conidia, and 2) pigmented fruiting structures embedded in the matrix of the substrate. The microbial metabolites deteriorate the substrates on which they grow resulting in the chemical and physical changes of the material bulk and surface, at times leading to structural weakening. We focused our studies on black stains which are prevalent on art rendered on paper, a subject that has received very little attention. Our techniques of analysis included three-dimensional topographic imaging and visualization, structural characterization and optical microscopy, scanning electron microscopy (SEM), and confocal laser scanning microscopy (CLSM).