Because of its high electronic conductivity, electrochemical stability, and optical transparency, fluorine-doped tin oxide (FTO) is a frequently used substrate for photoelectrochemical water splitting (PEC), dye-sensitized solar cells (DSSCs) and other electrocatalytic systems. These applications often require high surface-area substrates, but typical wet-chemical and lithographic approaches to nanostructure this promising material have been limited by the toxic fluorine ion and the resistance of tin oxide to standard chemical etchants. In this work, we develop a novel process to nanostructure commercial FTO by combining nanosphere lithography with argon ion-milling. We show nanostructured FTO with nanopillars of tunable height and diameter. Depositing tungsten oxide with atomic layer deposition on the nanostructured FTO substrate yields a PEC photoanode improvement of 40% over the baseline FTO substrate. The improvement is ascribed mainly to the increased roughness factor achieved by nanostructuring the substrate.