Rostering is central to the efficient running of any hospital and to the lives of its staff. We show how our rostering program improves staff cover and wellbeing for doctors in training in UK National Health Service (NHS) hospitals. By capturing the mathematical structure of the underlying dynamics, we were able to solve the problem to optimality with Mathematical Programming. The program was run with MPL-Gurobi optimisation software in the Cloud. A pilot study at a London Emergency Department demonstrated reduction in doctors’ fatigue, locum staff costs and rota manager’s time. Consistent staff cover improved doctors’ morale, and both contributed to better patient care. For surgical departments, carefully designed team rosters doubled training time and improved the continuity of care for the patients. These results demonstrate how training, progression and retention in the NHS can be significantly improved. This win-win-win scenario, for hospital, doctors and patients, provides a paradigm shift for rostering in hospitals.