A fast Fourier transform (FFT) based method is developed to model the pseudo-elastic behavior and shape-memory effect in phase transforming materials. An infinitesimal strain based variational FFT formulation is adapted and enhanced to enable the solution of nonlinear, stress-controlled and thermo-mechanical problems. The capabilities of the method are illustrated by implementing a computational homogenization approach to modeling the thermo-mechanical response of shape memory alloys with heterogeneities. The accuracy and performance of the method is evaluated by comparison with finite element (FE) solutions for single- and multi-particle cells subjected to various loading schemes. For the class of nonlinear problems of interest, the proposed method is shown to be an order of magnitude faster than the FE method for a given resolution, and possibly for the same accuracy.