Climate change is transforming coral reefs, threatening supply of essential dietary micronutrients from small-scale fisheries to tropical coastal communities. Yet the nutritional value of reef fisheries and climate impacts on micronutrient availability remain unclear, hindering efforts to sustain food and nutrition security. Here, we measure nutrient content in coral reef fishes in Seychelles and show that reef fish are important sources of selenium and zinc and contain levels of calcium, iron, and omega-3 fatty acids comparable with other animal-source foods. Using experimental fishing, we demonstrate that iron and zinc are enriched in fishes caught on regime-shifted macroalgal habitats, whereas selenium and omega-3 varied among species. We find substantial increases in nutrients available to fisheries over two decades following coral bleaching, particularly for iron and zinc after macroalgal regime shifts. Our findings indicate that, if managed sustainably, coral reef fisheries could remain important micronutrient sources along tropical coastlines despite escalating climate impacts.