Nanostructured Pb electrodes consisting of nanowire arrays were obtained by electrodeposition, to be used as negative electrodes for lead-acid batteries. Reduced graphene oxide was added to improve their performances. This was achieved via the electrochemical reduction of graphene oxide directly on the surface of nanowire arrays. The electrodes with and without reduced graphene oxide were tested in a 5 M sulfuric acid solution using a commercial pasted positive plate and an absorbed glass mat separator in a zero-gap configuration. The electrodes were tested in deep cycling conditions with a very low cut-off potential. Charge-discharge tests were performed at 5C. The electrode with reduced graphene oxide outperformed the electrode without reduced graphene oxide, as it was able to work with a very high utilization of active mass and efficiency. A specific capacity of 258 mAhg(-1)-very close to the theoretical one-was achieved, and the electrode lasted for more than 1000 cycles. On the other hand, the electrode without reduced graphene oxide achieved a capacity close to 230 mAhg(-1), which corresponds to a 90% of utilization of active mass.