The workplace is regarded as an ideal setting for health promotion, not least because large sections of the population, including “high risk groups”, can be reached. One group which is reportedly in great demand of health promotion is that of female (migrant) cleaners – the participants in our study. In this article we share information about the design and the evaluation of a worksite physical activity programme based on a social ecological approach to health promotion. Via participant observation and semi-structured interviews with 20 cleaners and their five supervisors we explored which factors constrained and which supported participation. The interviews revealed a high degree of appreciation for the training but also pointed to a number of constraints which were embedded into the participants’ biographies and everyday lives as migrant cleaners in Denmark. Most women had no previous experience with sport and exercise and struggled with the high demands at work and a “second shift” at home. As a consequence, most participants found the training too time- and energy-consuming. We conclude that exercise programmes should preferably be conducted at the workplace and during working hours.