Due to rise in infrastructure development and demand for seawater and sea sand concrete, fiber-reinforced polymer (FRP) rebars are widely used in the construction industry. Flexural strength is an important component of reinforced concrete structural design. Therefore, this research focuses on estimating the flexural capacity of FRP-reinforced concrete beams using novel artificial intelligence (AI) decision tree (DT) and gradient boosting tree (GBT) approaches. For this purpose, six input parameters, namely the area of bottom flexural reinforcement, depth of the beam, width of the beam, concrete compressive strength, the elastic modulus of FRP rebar, and the tensile strength of rebar at failure, are considered to predict the moment bearing capacity of the beam under bending loads. The models were trained using 60% of the database and were validated first-hand on the remaining 40% database employing the correlation coefficient (R), error indices namely, mean absolute error, root mean square error (MAE, RMSE) and slope of the regression line between observed and predicted results. The developed models were further validated using sensitivity and parametric analysis. Both models revealed comparable performance; however, based on the comparison of the slope of the validation data (0.83 for GBT model against 0.75 for the DT model) and higher R for the validation phase in case of the GBT model in comparison to the DT, the GBT model can be considered more accurate and robust. The sensitivity analysis yielded depth of the beam as the most influential parameter in contributing flexural strength of the beam, followed by the area of flexural reinforcement. The developed GBT model surpasses the existing gene expression programming (GEP) model in terms of accuracy; however, the current American Concrete Institute (ACI) model equations are more reliable than AI models in predicting the flexural strength of FRP-reinforced concrete beams.