Wild-caught fish provide an irreplaceable source of essential nutrients in food-insecure places. Fishers catch thousands of species, yet the diversity of aquatic foods is often categorized homogeneously as ‘fish’, obscuring an understanding of which species supply affordable, nutritious and abundant food. Here, we use catch, economic and nutrient data on 2,348 species to identify the most affordable and nutritious fish in 39 low- and middle-income countries. We find that a 100 g portion of fish cost between 10 and 30% of the cheapest daily diet, with small pelagic fish (herring, sardine, anchovy) being the cheapest nutritious fish in 72% of countries. In sub-Saharan Africa, where nutrient deficiencies are rising, <20% of small pelagic catch would meet recommended dietary fish intakes for all children (6 months to 4 years old) living near to water bodies. Nutrition-sensitive policies that ensure local supplies and promote consumption of wild-caught fish could help address nutrient deficiencies in vulnerable populations.