Coastal social ecological systems in eastern Africa are subject to a range of environmental, social and economic changes. They are already vulnerable to these multiple stressors, and the impacts of climate change are likely to further exacerbate their vulnerabilities. Some of these impacts may be observed and experienced already. The analysis presented in this paper is based on mixed methods empirical research exploring local perceptions of recent changes at four sites in coastal Tanzania and Mozambique. People recognise and rank a number of climate and non-climate stressors which have contributed towards more risky and less diverse livelihoods. Importantly, regional and international policy initiatives – in the form of river basin management in Mozambique and South Africa, and development of a Marine Protected Area in Tanzania – are perceived to further erode resilience and exacerbate vulnerabilities. We suggest this is a form of policy misfit, where policies developed to address a specific issue do not take account of cross-scale dynamics of change, the interactions between multiple stressors, nor longer term climate change. This policy misfit may be remedied by a move towards adaptive forms of governance, and necessitates an explicit focus on building the adaptive capacity of the poor and most vulnerable in society.