The paper presents a methodology for damage evaluation of fiber-reinforced concrete (FRC) exposed to elevated temperatures of 400 oC to 800 oC. The residual compressive strength fraction of cylindrical FRC specimens with a water–cement ratio of 0.47 and total fiber volume fraction of 1.2% was evaluated for mixtures with various proportions of steel and polypropylene fibers. The residual compressive strength fraction increased with the increase in the proportion of steel fiber at 400 oC. The residual strength fractions of mixtures with various fiber proportions changed less with increased exposure temperature. The effectiveness of visual inspection and ultrasonic nondestructive tests in assessing the effects of temperature exposure and the residual compressive strength fraction was evaluated. The experimental results indicate a potential application of the nondestructive tests on damage assessment of FRC with various mixture proportions. An equation for estimating the residual compressive strength fraction based on ultrasonic pulse velocity was developed.