Casualty rescue is always a critical issue in emergency departments when the buildings collapsing, bridges or roads damaged happen in the earthquakes. However, previous studies essentially considered such a problem by assuming fixed travel time for the ambulance. This paper aims to involve road failure during the earthquake by considering the stochastic durations for each road. The probability that the casualty can be successfully rescued to the casualty collection point (CCP) provides further medical treatment for the casualties. Such a probability is named network reliability which is defined as the probability that the number of casualties can be successfully transported to the CCP in a given rescue time. To evaluate the network reliability, the data transformation procedure is firstly developed to convert the road data into duration probability table, which addresses the travel time and corresponding probability of each road. Second, the multi-state rescue network is established, and an algorithm is constructed to obtain all upper bound vectors meeting the demand and time constraint. The network reliability can be computed by obtained upper bound vectors using the recursive sum disjoint product method. An example of a real earthquake disaster in Tainan City, Taiwan is adopted to demonstrate the practicality of the proposed algorithm. Finally, the experimental results with different number of ambulances and times can provide the commander decision recommendations for immediate emergency responses.