In the present study, the nonlinear dynamic analysis of beams on the fractional order viscoelastic nonlinear foundation subjected to a moving load with variable speed is elaborated. The D’Alembert principle is used to derive the governing equation using a large amplitude nonlinear Winkler foundation and the Caputo fractional viscoelastic model. A nonlinear fractional partial differential equation is resulted and the Galerkin procedure is adopted to reduce the governing equation to a coupled nonlinear fractional differential system. A well adapted explicit numerical procedure based on the central difference and a discrete fractional derivative approximation is elaborated allowing to consider an arbitrary number of modes. Due to the moving load effect a large number of eigenmodes is required for convergence of the time response. A detailed parametric study is conducted with the focus on the effects of the fractional derivative order and the nonlinear parameters. Moreover, the effects of various system parameters belonging to the application problems are investigated. It is revealed that the order of the fractional derivative and nonlinear foundation have significant effects on the vertical deflection of the beam.