This paper considers an extension of the classical p-center problem, called the p-next center problem with capacity and coverage radius constraints (pNCPCR). The p-next center problem is a facility location problem that deals with possible failures of centers where users first arrive at their closest reference center, realize the center’s failure on arrival, and are then forwarded to the closest backup center. The goal is to minimize the maximum distance traveled from a user to its reference center plus the distance from this reference center to the closest backup center. The pNCPCR additionally considers capacities of centers, user demands and a maximum travel distance for users. We state a revised mixed-integer quadratic program for the pNCPCR, which is solved using Gurobi, and propose a tabu search metaheuristic for solving larger instances of the problem. We develop an efficient evaluation of the neighborhood structure by using an auxiliary data structure and restrict the neighborhood by evaluating only promising solutions. Experiments on 1,652 instances show tabu search’s high performance, finding reliably high-quality solutions in short time. Tabu search outperforms Gurobi, with faster solution times, finding most proven optimal solutions in less than a second. Also, on medium-sized and large instances, tabu search finds significantly better feasible solutions than Gurobi. Compared to an earlier Biased Random Key Genetic Algorithm, our tabu search finds equally good solutions more quickly in most cases.