The nurse rostering problem is a very important problem to address. Due to the importance of nurses’ jobs, it is vital that all the nurses in a hospital are assigned to the most appropriate shifts and days so as to meet the demands of the hospital as well as to satisfy the requirements and requests of the nurses as much as possible. Nurse rostering is a computationally hard and challenging combinatorial optimisation problem. To solve it, general and efficient methodologies such as selection hyper-heuristics have emerged. To address the multi-stage nurse rostering formulation, posed by the second international nurse rostering competition’s problem, a sequence-based selection hyper-heuristic that utilises a statistical Markov model is developed. The proposed algorithm incorporates a dedicated algorithm for building feasible initial solutions and a series of low-level heuristics with different dynamics that respect the characteristics of the competition’s problem formulation. Empirical results and analysis suggest that the proposed approach has a significant potential on difficult problem instances.