In this paper, we address a districting problem motivated by a real-world case study to partition residential areas of a region for a healthcare system operation under interval demand uncertainty of health services. A mixed-integer programming model is presented based on the graph theory that enforces contiguity constraints on districts in addition to other corresponding practical criteria. Furthermore, robust optimization approaches are extended to address the existing uncertainty. To deal with the problem's computational intractability, an improved genetic algorithm is developed in accordance with the graph-based nature of the problem obtaining near-optimal solutions on large-sized instances. Extensive computational results are presented on a real-world case study and several randomly generated instances to evaluate the applicability of the models, performance of the presented robustness measure, and effectiveness of the solution approach. Furthermore, a hierarchical districting approach that enables decision makers to obtain districting decisions in various levels of health services is examined. Sensitivity analyses on main parameters are performed to derive some managerial insights that can help practitioners in providing suitable and homogeneous health services in a geographical area.