Recent discussions of healthy and sustainable diets encourage increased consumption of plants and decreased consumption of animal-source foods (ASFs) for both human and environmental health. Seafood is often peripheral in these discussions. This paper examines the relative environmental costs of sourcing key nutrients from different kinds of seafood, other ASFs, and a range of plant-based foods. We linked a nutrient richness index for different foods to life cycle assessments of greenhouse gas (GHG) emissions in the production of these foods to evaluate nutritional benefits relative to this key indicator of environmental impacts. The lowest GHG emissions to meet average nutrient requirement values were found in grains, tubers, roots, seeds, wild-caught small pelagic fish, farmed carp and bivalve shellfish. The highest GHG emissions per nutrient supply are in beef, lamb, wild-caught prawns, farmed crustaceans, and pork. Among ASFs, some fish and shellfish have GHG emissions at least as low as plants and merit inclusion in food systems policymaking for their potential to support a healthy, sustainable diet. However, other aquatic species and production methods deliver nutrition to diets at environmental costs at least as high as land-based meat production. It is important to disaggregate seafood by species and production method in ‘planetary health diet’ advice.