This article presents a reliable and robust rapidly exploring random tree (R2-RRT*) algorithm to tackle challenges in mission planning of off-road autonomous ground vehicles (AGVs) under uncertain terrain environment. Two types of mobility reliability metrics, namely state mobility reliability (SMR) and mission mobility reliability (MMR), are first defined to quantify the mobility reliability of an AGV and to incorporate mobility reliability into mission planning. SMR measures the probability that a vehicle can pass through a specific location on a map of interest, whereas MMR quantifies mobility reliability of a mission path with the consideration of dependence of soil properties and slope over space. Based on the defined SMR and MMR metrics, two reliability-based robust mission planning models are developed to identify optimal paths that have robust travel time and satisfy specific reliability requirements. Moreover, a reliability-based path smoothing algorithm is developed to address the suboptimality of R2-RRT*. Results of a case study demonstrate the efficacy of the proposed models and algorithms. Note to Practitioners —This article was motivated to explicitly account for the uncertain terrain environment in mission planning of off-road autonomous ground vehicles (AGVs). Existing approaches, e.g., RRT and its variants, in general, oversimplify the uncertainty sources and overlook the reliability of vehicle mobility. These simplifications could lead to failure (i.e., immobility) of off-road AGVs on the obtained paths. This article suggests a reliability-based mission planning model by incorporating the proposed SMR and MMR metrics into mission planning considering the spatial-dependent uncertainty sources. To identify a reliable and robust path, we extend RRT* to R2-RRT* that achieves a tradeoff between mission cost and reliability. The proposed reliability-based mission planning model, however, is not limited to RRT* and can also be integrated with other path planning algorithms. It can be also applied to other unmanned vehicles and robots, such as the motion planning of unmanned aerial vehicles (UAVs) in adverse weather conditions.