Prediction of rover mobility on soft soil has many applications ranging from mission planning to rover design. Finite Element Methods (FEM) for modeling wheel-terrain interactions provide detailed analysis with high computational cost. We present a novel approach that eliminates the need for FEM, while using elasto-plastic representations for soil. We propose a velocity field in the vicinity of the wheel-soil contact area motivated by the physical nature of the problem. Using this velocity field, the incremental strain tensor is determined in the contact area. The incremental changes to the stress field are then determined by resorting to elasto-plasticity theory and an appropriate constitutive relation for soil. As opposed to finite element approaches, this approach focuses on the wheel-soil contact patch only, which provides the basis for the development of fast algorithms. Due to the elasto-plastic representation for soil, energy dissipation during soil compaction is directly captured. In addition, the proposed approach uses generalized velocities of the wheel as inputs, which makes it compatible with dynamic models of multibody systems. The dynamic slip-sinkage behavior of the wheel and the semi-elliptical shape of the normal stress distribution under the wheel are natural outcomes of the proposed model. By combining this approach with a heightfield as terrain representation, elasto-plastic soil deformation and changes in the hardening state of soil are directly captured. In addition, the implementation of the new approach is readily parallelizable. This makes the model well suited for execution on modern multi-core architectures. Interactive and even real-time simulation of rovers on soft soil is possible. For model validation an extensive set of experiments was performed using the Juno II rover. The comparison of the experimental and simulation results show very good agreement for a broad range of slip ratios. These results will be illustrated in detail in this paper and in the presentation.