Materials coming from end-of-life tires (so-called Tire Recycled Materials—TRM) can provide a valuable contribution to enhance the circularity of mortars and concretes. Within a cementitious mixture, secondary rubber from end-of-life tires can partially substitute stone aggregates, which is scarce in some areas of the Earth. However, this substitution is not always effective. As the content of rubber increases, both the reduction of strength and the increment of the potential impact on climate change can be observed in cement-based composites. Accordingly, a new assessment procedure, based on the eco-mechanical analysis, is herein proposed for mortars containing TRM. The aim is to increase mechanical performance and the use of secondary materials, as well as to reduce the environmental impacts. As a result, through a suitable combination of both rubber and steel fibers from end-of-life tires, new mortars showing better structural and environmental performances can be introduced.