The ability of autonomous or semi-autonomous mobile robots to rapidly and accurately predict their mobility characteristics is an important requirement for their use in unstructured environments. Most methods for mobility prediction, however, assume precise knowledge of environmental (i.e. terrain) properties. In practical conditions, significant uncertainty is associated with terrain parameter estimation from robotic sensors, and this uncertainty must be considered in a mobility prediction algorithm. Here a method for efficient mobility prediction based on the stochastic response surface approach is presented that explicitly considers terrain parameter uncertainty. The method is compared to a Monte Carlo-based method and simulations show that the stochastic response surface approach can be used for efficient, accurate prediction of mobile robot mobility. ©2008 IEEE.