In the current work, XRD, SEM, EBSD and TEM techniques were used to evaluate the microstructure of stainless Fe-Mn-Si-Cr-Ni-Co shape memory steel processed by ECAE and annealed for one hour at temperatures ranging from 650ºC to 950ºC. The results were then correlated with the mechanical and shape-memory properties of the steel. It was observed that the samples containing large grains and a microstructure free of defects or precipitates presented a high volume fraction of multi-variant thermal martensite and stress-induced martensite, resulting in good shape recovery, owing to the memory effect. The grain refinement and precipitation of second-phase particles decreased the volume fraction and number of martensite variants and considerably increased the mechanical resistance, enhancing the elastic shape recovery. It was shown that shape memory properties were essentially related to the mechanical resistance of the matrix, which in turn was related to the microstructure.