To improve the strength loss caused by the incorporation of rubber particles into concrete, the mechanical properties of three kinds of rubber concrete (RC) were enhanced by adding scrap steel fiber with volume content of 0.5%~20%. The cube compressive strength, splitting tensile strength, four-point flexural strength, and axial compressive strength of each scrap steel fiber reinforced rubber concrete (SSFRC) at 28 d were tested. To measure the compressive toughness of SSFRC, the tensile-compressive ratio, flexural-compressive ratio, and toughness index were introduced. Macroscopic test results and SEM were used to analyze the mechanism of strengthening and toughening of RC mechanical properties by scrap steel fiber. The results show that adding rubber decreases the mechanical properties of concrete with various matrix strength. Adding steel fiber admixture causes a trend in the mechanical strength of SSFRC with various matrix strength to increase first and then decrease, getting the greatest compressive strength at 1.0%, the greatest tensile and flexural strength at 1.5% of steel fiber. Steel fiber and rubber particles can cooperate at a specific admixture amount to increase the toughness of RC. The local hydration of scrap steel fiber may have taken place, according to the microscopic morphology of the transition zone at the interface between the matrix and scrap steel fiber. In conclusion, the best mechanical strength enhancement effect and the best toughness of SSFRC are achieved at 10% of rubber and 1.5% of scrap steel fiber.