The increasing train traffic over railway networks stretches the demand for capacity of railway yards and rolling stock maintenance locations, which increasingly limits performance and further growth. Therefore, the scheduling of rolling stock maintenance and the choice regarding optimal locations to perform maintenance is increasingly complicated. This research introduces a Maintenance Scheduling and Location Choice Problem (MSLCP). It simultaneously determines maintenance locations and maintenance schedules of rolling stock, while considering the available capacity of maintenance locations. Solving the MSLCP using one large Mixed Integer Programming appears not to perform well enough. Therefore, to solve the MSLCP, an optimization framework based on Logic-Based Benders’ Decomposition (LBBD) is proposed by combining two models, the Maintenance Location Choice Problem (MLCP) and the Activity Planning Problem (APP), to assess the capacity of an MLCP solution. Within the LBBD, four variants of cut generation procedures are introduced to improve the computational performance: a naive procedure, two heuristic procedures and the so-called min-cut procedure that aims to exploit the specific characteristics of the problem at hand. The framework is demonstrated on realistic scenarios from the Dutch railways. It is shown that the best choice for the cut generation procedure depends on the objective: when aiming to find a good but not necessarily optimal solution, the min-cut procedure performs best, whereas when aiming for the optimal solution, one of the heuristic procedures is the preferred option. The techniques used in the current research are new to the current field and offer interesting next research opportunities.