Paper, like all other cultural heritage materials, degrades over time, but conservation slows down the rate of its deterioration. There is a long history of cooperation between microbiologists and conservators of libraries and archival materials, but current approaches addressing paper deterioration need urgent reassessment to take full advantage of modern microbiological methodologies. The present article discusses what we believe are the current priority research areas in assessing microbial risk to paper heritage, and reports studies on a 13th century Italian manuscript and on Leonardo da Vinci's Atlantic Codex which illustrate the problems and challenges encountered when dealing with microbial investigations of paper artworks. The potential of using a more advanced microbiological approach is highlighted.