We report the discovery of a temperature induced phase transition between the alpha and beta structures of antimonene. When antimony is deposited at room temperature on bismuth selenide, it forms domains of alpha-antimonene having different orientations with respect to the substrate. During a mild annealing, the beta phase grows and prevails over the alpha 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 free-standing alpha- and beta-antimonene only slightly differ, the beta phase is ultimately favoured in the annealed heterostructure due to an increased interaction with the substrate mediated by the perfect lattice match.