A series of self-assembled WO3-BiVO4 nanostructured thin films were grown on the (001) yttria-stabilized zirconia (YSZ) substrate at the substrate temperatures of 400 °C, 500 °C, 550 °C, 600 °C, 650 °C and 700 °C by a pulsed laser deposition method. The microstructures including crystalline phases, epitaxial relationships, surface morphologies and interface structures were investigated by a combination of x-ray diffraction, scanning electron microscopy and high-resolution transmission electron microscopy. The sample grown at 400 °C was amorphous due to the low driving forces for nucleation and diffusion. For the samples made at 500 °C, 550 °C and 600 °C, the monoclinic BiVO4 matrix epitaxially grew on YSZ, forming the matrix, where the WO3 nanopillars were embedded in with a specific orientation relationship among BiVO4, WO3 and YSZ. However, in thin films deposited at 650 °C and 700 °C, the WO3 grains randomly grew on the YSZ substrate, which dominated the microstructures of the resultant thin films. Quantitative analyses of the microstructures revealed that the lateral grain sizes of BiVO4 and WO3 increased and the volume fraction of BiVO4 in the thin films decreased with the increase of the deposition temperature. A three-regime growth mechanism of the WO3-BiVO4 composite thin film was proposed based on the growth dynamics determined by the competition between BiVO4 and WO3.