Restart failure is the major threat to the safe operation of waxy crude pipelines. This study introduces the reliability-based limit state method into the assessment of restart ability of waxy crude pipelines. A mathematical model for restart failure assessment was established which is based on the unsteady heat transfer and start-up flow during the shutdown and restart process. Further, an efficient and robust stochastic-numerical simulation algorithm has been developed, and a target safety level is recommended. Therefore, a quantitative assessment of the restart ability of waxy crude pipelines has been achieved. The application of this approach includes the determination of the restart failure probability of a pipeline shut down for a period, the determination of the maximum allowable time of pipeline shutdown corresponding to a target safety level, and the determination of the minimum pumping temperature of a crude corresponding to a maximum allowable time of pipeline shutdown. Compared with the traditional approaches to determining empirically the pumping temperature and maximum allowable time of pipeline shutdown, this study provides new support in theory and methodology for the safe and economical operation of waxy crude pipelines.