Carbon-metal-based composites arise as advanced materials in the frontiers with nanotechnology, since the properties inherent to each component are multiplexed into a new material with potential applications. In this work, a novel composite consisting of randomly oriented permalloy nanowires (Py NWs) intercalated among the sheets of multi-layered graphene oxide (GO) was performed. Py NWs were synthesized by electrodeposition inside mesoporous alumina templates, while GO sheets were separated by means of sonication. Sequential deposition steps of Py NWs and GO flakes allowed to reach a reproducible and stable graphene oxide-based magnetic assembly. Microscopic and spectroscopic results indicate that Py NWs are anchored on the surface as well as around the edges of the multi-layered GO, promoted by the presence of chemical groups, while magnetic characterization affords additional support to our hypothesis regarding the parallel orientation of the Py NWs with respect to the GO film, and also hints the parallel stacking of GO sheets with respect to the substrate. The most striking result remains on the electrochemical performance achieved by the composite that evidences an enhanced conductive behaviour compared to a standard electrode. Such effect provides an approach to the development of permalloy nanowires/graphene oxide-based electrodes as attractive candidates for molecular sensing devices.