This article addresses the periodic home health care (HHC) server assignment problem in HHC companies. This problem is a variant of the periodic vehicle routing problem with specific constraints for customers and servers (e.g., customers' requirements for multiple medical skills and continuous care offered by a given number of servers and servers' requirements for workload balance). Solving large-scale problems from practical applications of HHC companies within an acceptable computation time is challenging. Consequently, we develop an efficient region-partition-based algorithm to solve these large-scale problems. First, the algorithms assign customers and servers to many independent regions. Second, four different tabu search (TS) algorithms are designed to solve the optimization problem of each region. Finally, the algorithms iteratively adjust the assignment of customers and servers to regions and solve the problems of each region. The performances of different TS algorithms are discussed. The effectiveness of the proposed region-partition-based algorithm for large-scale problems is validated.