In a location-allocation system, it is necessary to obtain not only an efficient set of facility locations, but also an efficient relationship among the catchment areas. This is especially important in services that are hierarchical in nature and where there is a strong relationship between the different levels. In seeking an effective relation among the different levels, all the areas assigned to a particular facility at one hierarchical level should belong to one and the same district in the next level. This property leads to a “coherent” districting structure. In this paper the concept of coherence is introduced within a network location covering framework: the Coherent Covering Location Problem locates two hierarchical facility levels by maximizing the coverage while ensuring coherence. Adaptations of the model to different location patterns and computational experience are provided.