58% of Nairobi's population live in informal settlements in extremely poor conditions. Household air pollution is one of the leading causes of premature death and disease in these settlements. Regulatory frameworks and government budgets for household air pollution do not exist and humanitarian organisations remain largely inattentive and inactive on this issue. The purpose of this paper is to evaluate the effectiveness of potential indoor-air related policies, as identified together with various stakeholders, in lowering household air pollution in Nairobi's slums. Applying a novel approach in this context, we used participatory system dynamics within a series of stakeholder workshops in Nairobi, to map and model the complex dynamics surrounding household air pollution and draw up possible policy options. Workshop participants included community members, local and national policy-makers, representatives from parastatals, NGOs and academics. Simulation modelling demonstrates that under business-as-usual, the current trend of slowly improving indoor air quality will soon come to a halt. If we aim to continue to substantially reduce household PM2.5 levels, a drastic acceleration in the uptake of clean stoves is needed. We identified the potentially high impact of redirecting investment towards household air quality monitoring and health impact assessment studies, therefore raising the public's and the government's awareness and concern about this issue and its health consequences. Such investments, due to their self-reinforcing nature, can entail high returns on investment, but are likely to give 'worse-before-better' results due to the time lags involved. We also discuss the usefulness of the participatory process within similar multi-stakeholder contexts. With important implications for such settings this work advances our understanding of the efficacy of high-level policy options for reducing household air pollution. It makes a case for the usefulness of participatory system dynamics for such complex, multi-stakeholder, environmental issues.