We address the problem of locating primary health care centers integrating the outpatient medical service as a capacitated service and a set of uncapacitated complementary services such as nutrition counseling, dental care, mental health, clinical analysis, and imaging service. The objective is to locate new facilities or upgrade existing ones while the demand coverage of the complementary services is maximized and the total travel distance for the outpatient service allocation is constrained. The cost of opening new facilities and upgrading the existing ones is restricted to a budget. The problem is modeled as a variation of the maximal covering location problem with additional side constraints. In addition, two auxiliary bi-objective integer programming models are introduced to help identify the trade-off between the total travel distance and different budgets. A case study based on the public health care system of the northern zone of the State of Mexico, Mexico, is presented, including an assessment of the trade-off between the total travel distance and the allowed budget. Optimal solutions were found using CPLEX for a set of instances composed of 1,086 demand nodes, 294 current facilities, and 117 candidate locations. The auxiliary bi-objective programming models were solved by an augmented ε-constraint method. The empirical work shows the usefulness of the proposed models.