In Iran, thousands of tons of plastic and rubber materials are discarded as wastes each year. The accumulation of these wastes around metropolitan areas has become a major environmental problem for cities and countries across the globe. Thus, many efforts have been made in recent years to find ways to recycle waste plastic materials and eliminate them from the environment. In this regard, reusing recycled materials is a strategy to deal with this problem. Since these waste materials do not have a proper quality to be used for usual life purposes such as household items, thus the best application for these materials is to use them as aggregates in the construction industry. Furthermore, using waste rubber materials such as scrap tires in the concrete mix is regarded as one of the efficient ways to recycle these waste materials. In addition, substituting a fraction of natural aggregates in the concrete mix by waste materials is a promising strategy to deal with environmental problems associated with these materials. Given that the presence of waste aggregate in concrete degrades its properties, adding fibers to the concrete mix has been shown to improve the mechanical performance. Therefore, in the present study, the compressive strength of the concrete reinforced with steel fibers and containing recycled scrap tire rubber aggregate was evaluated after exposure to high temperatures through an experimental program. Here, a total of nine mix designs were prepared for the experimental phase, with the test variables being the volume percentage of tire rubber aggregate as a replacement for natural sand (0, 5, and 10%), the volume fraction of steel fibers (0, 0.5, and 1%), and temperature (20, 200, 400, and 600 °C). Moreover, the compressive strength values were compared with those predicted by the ACI 216 and EN 1994-1-2 codes. The results showed that adding steel fibers together with tire rubber aggregate in the concrete mix led to a decrease in the compressive strength of the heated and unheated concrete specimens. In addition, as temperature increased, the compressive strength of all the concrete specimens saw a considerable reduction. In this regard, after exposure to 600 °C, the compressive strength loss rate was higher compared to that after exposure to other temperatures, such that the compressive strength of the reference specimen and those containing tire aggregate and fibers decreased by 59.5-76.9% relative to that of the corresponding specimens at ambient temperature. ACI 216 and EN 1994-1-2 provide a relatively good estimation for the normalized compressive strength of all the concrete specimens containing tire rubber and steel fibers at 200 and 400 °C; however, they give an overestimation for the reference concrete. In addition, the above codes give a relatively good prediction for the normalized compressive strength of the specimens exposed to 600 °C (except for specimens ST0TR10, ST0.5TR10, and ST1.0TR5). Finally, by employing the response surface method (RSM), an optimum solution was proposed for the design parameters in which the compressive strength of the fiber-reinforced concrete containing recycled tire aggregate was maximized at different temperatures.