The shear capacity of reinforced concrete (RC) beams without stirrups is an important aspect in designing and assessing frame-type buildings. As a consequence, nearly all design codes provide equations for the evaluation of the concrete shear strength, mostly derived empirically from experimental data. In this regard, some recent studies have shown that code provisions in force might be unfit to capture adequately many trends and can become unsafe for practical applications. In light of the existing difficulties and uncertainties, the implementation of proper computational methods—together with the use of recent and qualified database of experimental data—is essential to carry out reliable formulations. In this paper, a new hybrid computational technique dubbed evolutionary polynomial regression is adopted to estimate the concrete shear strength for rectangular RC beams. It combines a genetic algorithm and the least squares regression in a way that considers complexity and fidelity to experimental data as conflicting criteria. A set of nondominated capacity models is first determined using a large experimental database. The capacity equation that provides the best compromise between accuracy and complexity is further elaborated in a statistical fashion to allow its potential use in building codes