This paper presents an experimental study on how crumb rubber particles from waste tires and corrugated round steel fibers affect the mechanical behavior of concrete. In addition to the standard plain mix and five combinations of mixes composed of 0.5%, 1.0%, and 1.5% ratios, three steel fiber and crumb rubber mixes, 0.5%, 1.0%, and 2.0% weight of sand, coarse aggregate, cement, and silica fume were evaluated. The percentage of silica fume that replaced the weight of the cement in this study was 8%. The fresh properties of the 12 mixtures in terms of slump and density were studied. After 28 days of curing 36 cubes, 36 cylinders, and 12 prisms, the hardened properties were determined by evaluating the mean compressive, split, and flexural strengths. The results indicate that a synergetic effect is observed for the combination of crumb rubber and corrugated round steel fibers to improve the fresh and hardened properties of concrete. Adding fiber reinforcement to concrete can mitigate the negative impacts of rubber, and vice versa. According to the combination content, increases in compressive strength, tensile strength, and flexural strength of up to 49.04%, 38.60%, and 75.76%, respectively, were achieved compared with the control combination. This validates the applicability of the proposed mathematical prediction formulation to evaluate the compressive strength, split tensile strength, and modulus of rupture of rubberized fibrous concrete in terms of fiber and rubber ratios. Based on these results, a promising solution for tire disposal is to recycle waste rubber for fibrous concrete applications.