|Last-mile logistics corresponds to the last leg of the supply chain, i.e., the delivery of goods to final cus-tomers, and they comprise the core activities of postal and courier companies. Because of their role in the supply chain, last-mile operations are critical for the perception of customers regarding the perfor-mance of the whole logistic process. In this sense, the sustained growth of e-commerce, which has been abruptly catalyzed by the irruption of the COVID-19 pandemic, has hanged the habits of customers and overtaxed the operational side of delivery companies, hindering their viability and forcing their adap-tation to the novel conditions. Many of these habits will remain after we overcome the sanitary crisis, which will permanently reshape the structure and emphasis of postal supply chains, demanding compa-nies to implement organizational and operational changes to adapt to these new challenges. In this work we address a last-mile logistic design problem faced by a courier and delivery company in Chile, although the same problem is likely to arise in the last-mile delivery operation of other postal companies, in particular in the operation of express delivery services. The operational structure of the company is based on the division of an urban area into smaller territories (districts) and the outsourcing of the delivery operation of each territory to a last-mile contractor. Because of the increasing volume of postal traffic and a decreasing performance of the service, in particular for the case of express deliveries, the company is forced to redesign its current territorial arrangement. Such redesign results in a novel optimization problem that resembles a classical districting problem with the additional quality of service requirements. This novel problem is first formulated as a mathematical programming model and then a specially tailored heuristic is designed for solving it. The proposed approach is tested on instances from the real-life case study, and the obtained results show significant improvements in terms of the percent-age of on-time deliveries achieved by the proposed solution when compared to the current districting design of the company. By performing a sensitivity analysis considering different levels of demand, we show that the proposed approach is effective in providing districting designs capable of enduring signifi-cant increases in the demand for express postal services.