This study assesses the tsunami hazard potential in Padang, Indonesia probabilistically using a novel stochastic tsunami simulation method. The stochastic tsunami simulation is conducted by generating multiple earthquake source models for a given earthquake scenario, which are used as input to run Monte Carlo tsunami simulation. Multiple earthquake source models for three magnitude scenarios, i.e., Mw 8.5, Mw 8.75, and Mw 9.0, are generated using new scaling relationships of earthquake source parameters developed from an extensive set of 226 finite-fault models. In the stochastic tsunami simulation, the effect of incorporating and neglecting the prediction errors of earthquake source parameters is investigated. In total, 600 source models are generated to assess the uncertainty of tsunami wave characteristics and maximum tsunami wave height profiles along coastal line of Padang. The results highlight the influence of the uncertainty of the scaling relationships on tsunami simulation results and provide a greater range of tsunamigenic scenarios produced from the stochastic tsunami simulation. Additionally, the results show that for the future major earthquakes in the Sunda megathrust, the maximum tsunami wave height in Padang areas can reach 20 m and, therefore, significant damage and loss may be anticipated in this region.