Self-assembled WO3-BiVO4 nanostructured thin films were grown on a (001) yttrium stabilized zirconia (YSZ) substrate by the pulsed laser deposition method with and without the indium tin oxide (ITO) bottom electrode. Their microstructures including surface morphologies, crystalline phases, epitaxial relationships, interface structures, and composition distributions were investigated by scanning electron microscopy, high-resolution transmission electron microscopy, and X-ray energy dispersive spectroscopy. In both samples, WO3 formed nanopillars embedded into the monoclinic BiVO4 matrix with specific orientation relationships. In the sample with the ITO bottom electrode, an atomically sharp BiVO4/ITO interface was formed and the orthorhombic WO3 nanopillars were grown on a relaxed BiVO4 buffer layer with a mixed orthorhombic and hexagonal WO3 transition layer. In contrast, a thin amorphous layer appears at the interfaces between the thin film and the YSZ substrate in the sample without the ITO electrode. In addition, orthorhombic Bi2WO6 lamellar nanopillars were formed between WO3 and BiVO4 due to interdiffusion. Such a WO3-Bi2WO6-BiVO4 double heterojunction photoanode may promote the photo-generated charge separation and further improve the photoelectrochemical water splitting properties.