Coral reefs support the livelihood of millions of people especially those engaged in marine fisheries activities. Coral reefs are highly vulnerable to climate change induced stresses that have led to substantial coral mortality over large spatial scales. Such climate change impacts have the potential to lead to declines in marine fish production and compromise the livelihoods of fisheries dependent communities. Yet few studies have examined social vulnerability in the context of changes specific to coral reef ecosystems. In this paper, we examine three dimensions of vulnerability (exposure, sensitivity, and adaptive capacity) of 29 coastal communities across five western Indian Ocean countries to the impacts of coral bleaching on fishery returns. A key contribution is the development of a novel, network-based approach to examining sensitivity to changes in the fishery that incorporates linkages between fishery and non-fishery occupations. We find that key sources of vulnerability differ considerably within and between the five countries. Our approach allows the visualization of how these dimensions of vulnerability differ from site to site, providing important insights into the types of nuanced policy interventions that may help to reduce vulnerability at a specific location. To complement this, we develop framework of policy actions thought to reduce different aspects of vulnerability at varying spatial and temporal scales. Although our results are specific to reef fisheries impacts from coral bleaching, this approach provides a framework for other types of threats and different social-ecological systems more broadly.