This study proposes a method of evaluating the robustness of a road network against a natural disaster and aims to determine the optimal allocation of medical facilities if road network degradation occurs because of severe natural disasters. Connectivity vulnerability and accessibility are important concepts in evaluating the strength and reliability of road networks. This paper first introduces a new network evaluation measure, the distinct paths–based accessibility index (DPAI), which is based on the concepts of both connectivity vulnerability and accessibility; considers the number of distinct paths between a certain origin–destination pair, free-flow travel time, and the number of opportunities in an area; and develops a solution algorithm. A medical facility location model that optimizes the allocation of a medical facility to each centroid according to the DPAI is then formulated, and the results are applied to a real network. Although the optimal allocation of a medical facility varies according to the minimum DPAI, the robustness of an actual network may be improved by reallocating medical facilities. Moreover, the allocation results depend on the value of the importance placed on the number of distinct paths. These results imply that it is critical to set the parameter on the importance of the number of distinct paths by considering risks and geographical features in the subject area.