A new nonlinear model was developed to evaluate the shear resistance of steel fiber-reinforced concrete beams (SFRCB) using linear genetic programming (LGP). The proposed model relates the shear strength to the geometrical and mechanical properties of SFRCB. The best model was selected after developing and controlling several models with different combinations of the influencing parameters. The models were developed using a comprehensive database containing 213 test results of SFRC beams without stirrups obtained through an extensive literature review. The database includes experimental results for normal and high-strength concrete beams. To verify the applicability of the proposed model, it was employed to estimate the shear strength of a part of test results that were not included in the modeling process. The external validation of the model was further verified using several statistical criteria recommended by researchers. The contributions of the parameters affecting the shear strength were evaluated through a sensitivity analysis. The results indicate that the LGP model gives precise estimates of the shear strength of SFRCB. The prediction performance of the model is significantly better than several solutions found in the literature. The LGP-based design equation is remarkably straightforward and useful for pre-design applications.