Seafood is an important source of bioavailable micronutrients supporting human health, yet it is unclear how climate change will influence its availability. Here, combining observational databases and predictive models, we assess nutrient availability from fisheries and mariculture in the past, and project their future under climate change. Since the 1990s, availability of iron, calcium, omega-3 and protein from seafood has declined, with increasing contributions of invertebrates and mariculture failing to compensate for these loses. Nutrient availability is projected to decrease at a rate of 10 - 12% per degree Celsius of warming in low-income countries where they are already highly dependent on seafood-derived nutrients. We demonstrate the importance of achieving the Paris Agreement to supporting nutritional security and global health equity, particularly for low-income nations.