Multi-modal transportation may be a solution in the immediate aftermath of a disaster when transportation resources are scarce. This study presents a multi-modal relief distribution model using a three-level chain composed of (1) supply nodes, (2) logistics operational areas, and (3) affected areas, while considering multiple trips for disaster response operations. The model determines the location of logistics operational areas, modes of transport utilized, and amount of relief goods allocated for each mode of transport. In addition, the model considers the different phases of essential response factors, such as network and infrastructure conditions, as well as accessibility of supplies and modes of transport. Data from the Yogyakarta Earthquake of 2006 in Indonesia are examined, revealing 11 selected logistics operational areas in which all modes of transport were utilized for relief delivery—mainly trucks and airplanes. For all goods delivered, multi-modal transportation comprised 45.67% of total use (31.98% for airplane–truck, 7.95% for sea vessels–truck, and 5.74% for airplane–helicopter). The results provide an example for decision makers regarding relief distribution systems with multi-modal transportation.