We investigate the variational structure of a phenomenological model for the coupled thermomechanical behavior of shape-memory polycrystalline materials. The nonisothermal evolution of the medium is reformulated as a generalized gradient flow of the entropy with respect to an entropy-production potential. Based on this reformulation, a semi-implicit time-discretization of the fully coupled thermomechanical problem is presented and proved to be unconditionally stable and convergent. The flexibility and robustness of the numerical method is assessed via both uniaxial and multiaxial computational tests.