In many retail industries, the retailer can choose the inventory location or fulfillment center (FC) that fulfills an order, yielding opportunities for inventory pooling and product selection expansion. However, fulfillment decisions are complex and must consider cost and speed, among various factors. With the unprecedented growth of the retail industry, companies must look for strategies that tackle the scale and complexity of fulfillment decisions. Regionalization is one such strategy, which divides the fulfillment network into a set of inter-connected regions: orders that originate within a region are primarily fulfilled by centers associated with the region. This structure simplifies the design of the fulfillment network, and has recently provided retailers with significant gains in cost and speed. In this study, we propose an optimization model to design the regions while simultaneously assigning fulfillment centers to match each region’s demand; to our knowledge, this is a novel problem that has not been studied in the literature. Two of the model’s main challenges include a non-linear objective function and contiguity constraints on the regions. We propose a local search heuristic to solve the problem at scale, along with efficient lower bounds to benchmark solution quality. Furthermore, we demonstrate that choosing appropriate parameters for designing regions can have a significant effect on solution quality, and can result in more demand being fulfilled within service guarantee deadlines.