Urban last-mile distribution in emerging economies suffers from unique levels of operational complexity, largely due to the prevailing dominance of the highly fragmented traditional retail channel. To support companies in strategically designing efficient urban distribution networks in such uncertain market environments, we propose a large-scale stochastic mixed integer linear programming model that incorporates three commonly deployed measures of physical distribution flexibility. Being able to flexibly adjust transportation capacities, facility capacities, and demand allocations may enable companies to serve urban markets more efficiently, especially in the presence of demand uncertainty. The model supports strategic network design decisions by optimizing the number, type, and capacity of distribution facilities as well as the composition of corresponding vehicle fleets. We apply the model to two large-scale, real-world case studies based on real data from Coca-Cola Femsa’s last-mile operations in Bogotá and Cali, Colombia. These case studies are representative for many last-mile distribution problems in emerging market megacities. Our numerical results demonstrate how considering stochasticity and incorporating physical distribution flexibility in the strategic design of urban last-mile distribution networks jointly and independently affect the resulting network design and improve its commercial and operational performance. The stochastic design approach outperforms the deterministic design approach on every instance in terms of expected cost and performance risk. In most cases, physical distribution flexibility improves performance. However, we show that in some cases, if strategic decisions are based on deterministic assumptions, allowing for operational flexibility may result in a deterioration in network performance.