Direct observations using scanning transmission electron microscopy unveil an intriguing interfacial bi-layer that enables epitaxial growth of a strain-free, monoclinic, bronze-phase VO2(B) thin film on a perovskite SrTiO3 (STO) substrate. We observe an ultrathin (2-3 unit cells) interlayer best described as highly strained VO2(B) nanodomains combined with an extra (Ti,V)O2 layer on the TiO2 terminated STO (001) surface. By forming a fully coherent interface with the STO substrate and a semi-coherent interface with the strain-free epitaxial VO2(B) film above, the interfacial bi-layer enables the epitaxial connection of the two materials despite their large symmetry and lattice mismatch.