This study takes the advantage of ultrasonic pulse velocity (UPV) in characterizing the mechanical properties of steel fiber-reinforced concrete (SFRC) containing recycled nylon granule (NG) and natural zeolite. A total of 216 specimens were prepared with 0, 0.75, and 1.25% volume fractions of steel fiber; 0, 10, and 20% of sand volume replaced with NG; and 10, 15, and 20% of cement weight substituted with micronized zeolite. The specimens were then exposed to temperatures of 20, 300, and 600 °C. The effect of each parameter (fiber, NG, zeolite, and temperature) was examined individually on the compressive and tensile strength, as well as the pulse velocity in the specimens. In addition, SEM and EDAX tests were successfully carried out on the specimens to investigate the interfacial microstructures in more detail. The obtained measures were also compared with EN 1994-1-2 and ACI 216 recommendations, and thus, several models were developed in terms of variables under consideration. The results revealed that adding NG to SFRC reduces its mechanical properties, particularly after exposure to elevated temperatures. However, incorporating steel fiber and natural zeolite not only counterweighs the induced reduction but also improves the properties of SFRC as compared to control specimens.