The motion of nanoparticles on soft surfaces is the result of interplay between capillary, elastic and friction forces. To elucidate the importance of the different contributions controlling nanoparticle rolling dynamics on soft surfaces, we performed molecular dynamics simulations of solid nanoparticles in contact with soft elastic substrates. The nanoparticle motion is initiated by applying a constant force resulting in stationary, steady rolling, and accelerating states, depending on the nanoparticle-substrate work of adhesion, W, the magnitude of the net applied force, F, and the substrate shear modulus G. In the stationary state, the restoring torque produced in the contact area balances the torque due to the external force. The rolling force Fr, determining the crossover to the rolling state, is proportional to the product of the work of adhesion W and nanoparticle size Rp, Fr ∼ WRp. In the steady rolling state, F > Fr, the nanoparticle maintains a constant rolling velocity which is a manifestation of the balance between the rolling friction force and the applied force. The observed scaling relationships between the applied force and nanoparticle velocity reflect a viscoelastic nature of the substrate deformation dynamics. A nanoparticle begins to accelerate when the energy supplied to the nanoparticle exceeds the energy dissipated in the contact area due to viscoelastic substrate deformation. Using these simulation results, we have constructed a diagram of states in terms of the dimensionless parameters F/WRp and W/GRp.