We have explored AuNPs (13 nm) both as a catalyst and as a core for synthesizing water-dispersible and highly stable core-shell structural Gold@Prussian Blue (Au@PB) nanoparticles (NPs). Systematic characterization by transmission electron microscopy (TEM) and X-ray photoelectron spectroscopy (XPS) disclosed AuNPs coated uniformly by a 5 nm thick PB layer. Au@PB NPs were attached to single-layer graphene oxide (GO) to form Au@PB decorated GO sheets. The resulting hybrid material was filtered layer-by-layer into flexible and free-standing GO paper, which was further converted into conductive reduced GO (RGO)/Au@PB paper via hydrazine vapour reduction. High-resolution TEM images suggested that RGO papers are multiply sandwich-like structures functionalized with core-shell NPs. Resulting sandwich functionalized graphene papers have high conductivity, sufficient flexibility, and robust mechanical strength, which can be cut into free-standing electrodes. Such electrodes, used as non-enzymatic electrochemical sensors, were tested systematically for electrocatalytic sensing of hydrogen peroxide. The high performance was indicated by some of the key parameters, for example the linear H2O2 concentration response range (1-30 μM), the detection limit (100 nM), and the high amperometric sensitivity (5 A cm−2 M−1). With the advantages of low cost and scalable production capacity, such graphene supported functional papers are of particular interest in the use as flexible disposable sensors.