Hexagonal perovskites are an attractive family of materials due to their various polymorphs and rich structure–property relationships. BaRuO3 (BRO) is a prototypical hexagonal perovskite, in which the electromagnetic properties are significantly modified depending on its lattice structure. Whereas thin-film synthesis would allow the study of the diverse properties of hexagonal perovskites by epitaxially stabilizing various metastable polymorphs, the epitaxial growth of hexagonal perovskites, especially at the initial growth stage, is yet to be addressed. In this study, it is shown that an intriguing nucleation behavior takes place during the initial stabilization of a hexagonal 9R BRO thin film deposited on a (111) SrTiO3 (STO) substrate. It is found that a nanoscale strained layer composed of different RuO6 octahedral stacking is initially formed at the interface followed by a relaxed single crystal 9R BRO thin film. Within the interface layer, hexagonal BRO is nucleated on the (111) STO substrate by both face- and corner-sharing octahedra. More interestingly, it is found that boundaries between differently stacked nucleation layers (heterostructural boundaries) facilitate strain relaxation, in addition to the formation of conventional misfit dislocations evolved from homostructural boundaries. The observations reveal an important underlying mechanism to understand the thin-film epitaxy and strain accommodation in hexagonal perovskites.