We introduce the Expeditionary Logistics Network Design Problem (ELNDP), a new formulation for operational-level planning in expeditionary environments where multi-modal vehicle coordination is critical and penalties for unmet demand dominate transportation costs. ELNDP extends the classical Scheduled Service Network Design Problem by incorporating flexible commodity sourcing and heterogeneous vehicle capabilities, both essential in military logistics. We propose an iterative refinement algorithm based on dynamic discretization discovery (DDD) that iteratively constructs consolidation plans on partially time-expanded networks. Unlike the classical DDD framework, our approach overestimates arc travel times and introduces backward recovery arcs to compute relaxed solutions. We also develop a new procedure for eliminating illegal vehicle cycles arising from explicit vehicle management, and introduce acceleration techniques based on capacity factors and a multi-commodity maximum-flow heuristic. A case study on 53 realistic instances designed with the United States Marine Corps shows that our method increases demand fulfillment by 106.4% and reduces solve times by 28.7% on average compared to benchmark approaches. Finally, our analysis offers managerial insights on how multi-modal coordination, time-discretization granularity, and proactive vehicle repositioning can substantially enhance responsiveness and resource utilization in expeditionary logistics operations.