The disposal of rubber waste poses a significant environmental challenge, and its reuse in the production of green concrete offers a sustainable solution. This study explores the mechanical behavior of fiber-reinforced concrete incorporating recycled crumb rubber (CR) as a partial aggregate replacement. Three types of fibers—polypropylene, macro-synthetic (MS), and steel (ST)—were combined with CR in different particle sizes (0-1 mm, 1-3 mm, and 3-5 mm) to evaluate their impact on the concrete's performance. The optimal fiber proportions were determined, and the effects of varying CR particle sizes on workability, compressive strength, and tensile strength were assessed. The results showed that the inclusion of fibers reduced workability, with PP fibers causing the most significant reduction (up to 80%). CR further decreased workability, particularly at higher particle sizes and percentages. In terms of mechanical performance, the compressive and tensile strengths of fiber-reinforced concrete improved by 22–27% and 22–59%, respectively. However, the addition of CR alone led to reductions in compressive and tensile strengths of up to 60% and 15%, respectively. Notably, the combination of fibers and CR enhanced concrete performance, with compressive strength increasing by up to 14% and tensile strength by 35% when using the optimal fiber content and 5% CR.