Micronutrient deficiencies constitute a pressing public health concern, especially in developing countries. As a dense source of bioavailable nutrients, aquatic foods can help alleviate such deficiencies. Developing aquaculture that provides critical micronutrients without sacrificing the underlying environmental resources that support these food production systems is therefore essential. Here, we address these dual challenges by optimizing nutrient supply while constraining the environmental impacts from aquaculture. Using life cycle assessment and nutritional data from Indonesia, a top aquaculture producer, we sought to identify aquaculture systems that increase micronutrient supplies and reduce environmental impacts (e.g., habitat destruction, freshwater pollution, and greenhouse gas emissions). Aquaculture systems in Indonesia vary more by environmental impacts (e.g. three order of magnitude for fresh water usage) than by nutritional differences (approximately +/- 50% differences from mean relative nutritional score). Nutritional-environmental tradeoffs exist, with no single system offering a complete nutrition-environment win-win. We also find that previously proposed future aquaculture paths sub optimally balance nutritional and environmental impacts. Instead, we identify optimized aquaculture production scenarios for 2030 with nutrient per gram densities 105-320% that of business-as-usual production and with environmental impacts as low as 25% of those of business-as-usual. In these scenarios Pangasius fish (Pangasius hypophthalmus) ponds prove desirable due to their low environmental impacts, but average relative nutrient score. While the environmental impacts of the three analyzed brackish water systems range from average to high compared to other aquaculture systems, their nutritional attributes render them necessary when maximizing all nutrients except vitamin A. Common carp (Cyprinus carpio) ponds also proved essential in maximizing zinc and omega n-3, while Tilapia (Oreochromis niloticus) cages were necessary in optimizing the production of calcium and vitamin A. These optimal aquaculture strategies also reduce business-as-usual demand for wild fish-based feed by 0-30% and mangrove expansion by 0-75% with no additional expansion into inland open waters and freshwater ponds. As aquaculture production expands globally, optimization presents a powerful opportunity to reduce malnutrition rates at reduced environmental impacts. The proposed reorientation promotes UN sustainable development goals 2 (zero hunger), 3 (health), 13 (climate action) and 14 (life under water) and requires concerted and targeted policy changes.