Tunable nanostructures that feature a high surface area are firmly attached to a conducting substrate and can be fabricated efficiently over significant areas, which are of interest for a wide variety of applications in, for instance, energy storage and catalysis. We present a novel approach to fabricate Fe nanoparticles using a pulsed-plasma process and their subsequent guidance and self-organization into well-defined nanostructures on a substrate of choice by the use of an external magnetic field. A systematic analysis and study of the growth procedure demonstrate that nondesired nanoparticle agglomeration in the plasma phase is hindered by electrostatic repulsion, that a polydisperse nanoparticle distribution is a consequence of the magnetic collection, and that the formation of highly networked nanotruss structures is a direct result of the polydisperse nanoparticle distribution. The nanoparticles in the nanotruss are strongly connected, and their outer surfaces are covered with a 2 nm layer of iron oxide. A 10 μm thick nanotruss structure was grown on a lightweight, flexible and conducting carbon-paper substrate, which enabled the efficient production of H2 gas from water splitting at a low overpotential of 210 mV and at a current density of 10 mA/cm2.