Polymer wastes are categorized as highly recyclable materials from various aspects. An effective way to recycle these materials is to utilize them in the concrete industry to replace aggregates. Thus, the non-renewable natural resources are reserved, and the waste disposal problems are partly mitigated. This study investigates the flexural response of steel fiber-reinforced concrete (SFRC) incorporating recycled nylon granules (NG) and natural zeolite after exposure to elevated temperatures. In total, 216 specimens were produced, which contained steel fiber at 0, 0.75, and 1.25% of mix volume, NG at 0, 10, and 20% of sand volume, and a type of zeolitic framework at 10, 15, and 20% of cement weight to examine the effect of each variable on the compressive and flexural strength, stiffness, and load–deflection response of concrete mixes. A concise microstructural analysis was also conducted to characterize the microscopic properties of the concrete constituent materials using SEM, BSEM, and EDXMA spectroscopy. The obtained results indicated that adding natural zeolite to the concrete mixes improved the compressive and flexural strength, as well as the flexural stiffness capacity. It was also observed that NG helped enhance the flexural specifications of specimens at 300 ◦C. This was attributed to the clamping action of partially molten polymer, similar to the crack-bridging mechanism of the steel fibers. The ultimate deflection capacity of the specimens was also increased with increasing zeolite addition.