This paper proposes an evolutionary approach for optimizing crew roster recovery (CRR) problems, in which rosters for multiday flight duties are reassigned after disruptions, under a set of constraints involving practical management issues, safety regulations, and preallocated activities. In the proposed approach, CRR problems are first formulated as combinational optimization problems containing multiple objectives and constraints, and a variant of the nondominated sorting genetic algorithm II method is used to explore Pareto solutions. To analyze the effectiveness of the proposed approach, a real-world rostering problem was studied. For the test instance, experimental results showed the advantages of the proposed approach compared with previous work in the literature. By simulating disruption events on the real-world rostering plan, we studied two recovery scenarios containing sufficient and insufficient available crews in the experiments. In particular, a constraint-loosening mechanism that conditionally replaced preallocated tasks with flight duties was proposed in a resource-shortage case to explore the Pareto solutions. The experimental results show that the proposed approach attains a favorable solution quality and can generate multiple recovery plans for decision makers.