We report the discovery of a temperature-induced phase transition between the α and β structures of antimonene. When antimony is deposited at room temperature on bismuth selenide, it forms domains of α-antimonene having different orientations with respect to the substrate. During a mild annealing, the β phase grows and prevails over the α phase, eventually forming a single domain that perfectly matches the surface lattice structure of bismuth selenide. First-principles thermodynamics calculations of this van der Waals heterostructure explain the different temperature-dependent stability of the two phases and reveal a minimum energy transition path. Although the formation energies of freestanding α- and β-antimonene only slightly differ, the β phase is ultimately favored in the annealed heterostructure due to an increased interaction with the substrate mediated by the perfect lattice match.