The potential of advanced tree-based models and optimized deep learning algorithms to predict fluvial bedload transport was explored, identifying the most flexible and accurate algorithm, and the optimum set of readily available and reliable inputs. Using 926 datasets for 20 rivers, the performance of three groups of models was tested: (1) standalone tree-based models Alternating Model Tree (AMT) and Dual Perturb and Combine Tree (DPCT); (2) ensemble tree-based models Iterative Absolute Error Regression (IAER), ensembled with AMT and DPCT; and (3) optimized deep learning models Long Short-Term Memory (LSTM) and Recurrent Neural Network (RNN) ensembled with Grey Wolf Optimizer. Comparison of the predictive performance of the models with that of commonly used empirical equations and sensitivity analysis of the driving variables revealed that: (i) the coarse grain-size percentile D90 was the most effective variable in bedload transport prediction (where Dx is the xth percentile of the bed surface grain size distribution), followed by D84, D50, flow discharge, D16, and channel slope and width; (ii) all tree-based models and optimized deep learning algorithms displayed ‘very good’ or ‘good’ performance, outperforming empirical equations; and (iii) all algorithms performed best when all input parameters were used. Thus, a range of different input variable combinations must be considered in the optimization of these models. Overall, ensemble algorithms provided more accurate predictions of bedload transport than their standalone counterpart. In particular, the ensemble tree-based model IAER-AMT performed most strongly, displaying great potential to produce robust predictions of bedload transport in coarse-grained rivers based on a few readily available flow and channel variables.