Many large e-commerce retailers now have the scale to operate their own middle mile consolidation networks, moving customer shipments from stocking locations to last mile delivery partners using a private set of freight transportation loads that reduce outbound logistics cost. In this article, we study a middle mile network design problem with fixed origins and destinations to determine minimum cost consolidation plans that satisfy customer shipment lead time constraints. We propose models where both input demands and planned load decisions are expressed as constant rates per time, extending traditional flat network service network design mixed-integer programs (MIPs) to capture waiting delays between load dispatches to ensure shipment lead time requirements are satisfied in expectation. We further generalize these models and propose techniques to adjust lead time constraints to ensure that specified shipment on-time arrival likelihoods are met. To find high-quality solutions to the difficult-to-solve MIPs we propose, we develop an effective integer-programming-based local search (IPBLS) heuristic that iteratively improves a solution by optimizing over a smartly selected subset of commodities. For the largest problem instances, we propose a two-phase IPBLS heuristic that first utilizes a simplified, restricted MIP that constrains leg waiting delays individually. The second phase then improves the best first-phase solution using the unrestricted MIP. Computational experiments using data from a large U.S.-based e-commerce partner demonstrate the significant impact of tight lead time constraints on the structure of the consolidation network designs and their concomitant operating costs. Notably, tighter constraints lead to solutions with increased shipment consolidation and higher dispatch frequencies on selected key transportation lanes. Such solutions trade off higher shipment transit times with significantly reduced shipment waiting times to meet lead time constraints at lower cost.