Graphene platelet networks (GPNs) comprised of randomly oriented graphene flakes two to three atomic layers thick are synthesized using a novel plasma-based approach. The approach uses a substrate capable of withstanding synthesis temperatures around 800 °C, but is fully independent of the substrate material. The synthesis occurs directly on the substrate surface without the necessity of any additional steps. GPNs were synthesized on various substrate materials including silicon (Si), thermally oxidized Si (SiO2), molybdenum (Mo), nickel (Ni) and copper (Cu), nickel-chromium (NiCr) alloy and alumina ceramics (Al2O3). The mismatch between the atomic structures of sp2 honeycomb carbon networks and the substrate material is fully eliminated shortly after the synthesis initiation, namely when about 100 nm thick deposits are formed on the substrate. GPN structures synthesized on a substrate at a temperature of about 800 °C are significantly more porous in comparison to the much denser packed amorphous carbon deposits synthesized at lower temperatures. The method proposed here can potentially revolutionize the area of electrochemical energy storage by offering a single-step direct approach for the manufacture of graphene-based electrodes for non-Faradaic supercapacitors. Mass production can be achieved using this method if a roll-to-roll system is utilized.