Hexagonal perovskites are an attractive group of materials due to their various polymorph phases and rich structure-property relationships. BaRuO3 (BRO) is a prototypical hexagonal perovskite, in which the electromagnetic properties are significantly modified depending on its atomic structure. Whereas thin-film epitaxy would vastly expand the application of hexagonal perovskites by epitaxially stabilizing various metastable polymorphs, the atomic structure of epitaxial hexagonal perovskites, especially at the initial growth stage, has rarely been investigated. In this study, we show that an intriguing nucleation behavior takes place during the initial stabilization of a hexagonal perovskite 9R BaRuO3 (BRO) thin film on a (111) SrTiO3 (STO) substrate. We use high-resolution high-angle annular dark field scanning transmission electron microscopy in combination with geometrical phase analysis to understand the local strain relaxation behavior. We find that nano-scale strained layers, composed of different RuO6 octahedral stacking, are initially formed at the interface, followed by a relaxed single crystal9R BRO thin film. Within the interface layer, hexagonal BROs are nucleated on the STO (111) substrate by both corner- and face-sharing. More interestingly, we find that the boundaries between the differently-stacked nucleation layers, i.e. heterostructural boundaries facilitates strain relaxation, in addition to the formation of conventional misfit dislocations evolving from homostructural boundaries. Our observations reveal an important underlying mechanism to understand the thin-film epitaxy and strain accommodation in hexagonal perovskites.