Prussian blue (PB) and its analogues are widely studied because of their interesting and promising magnetic and optical properties. The pigment Prussian blue, found in different types of artworks (paintings, watercolors and photographs), is also studied in the area of heritage science, where its capricious fading behavior under light or anoxia treatment poses problematic conservation issues. PB fading is due to the reduction of iron(III) to iron(II) and depends significantly on the artefact. This paper focuses on the roles of the substrate in affecting the PB structure and modifying the redox process. In particular, X-ray absorption experiments at the Fe K-edge of unfaded and faded PB–paper samples show that changes in the PB structure can happen by simple contact with the substrate, prior to the fading treatment. Spectrophotometric measurements on a series of model PB–paper samples further demonstrate the multiple influences of the substrate and show that not only its chemical composition but also its role as a dispersion and textured medium significantly alter the fading behavior of PB. A potential roadmap is proposed to rationally investigate the complex fading process of Prussian blue on a substrate.