Food production greatly contributes to greenhouse gas emissions (GHG), but there remain concerns that consuming environmentally sustainable foods can increase the likelihood of nutritional deficiencies during pregnancy. We identified commonly consumed foods of pregnant women and determined the effect of their replacement with environmentally sustainable alternatives on nutrient intake and measures of environmental sustainability. Dietary intake data from 171 pregnant women was assessed and foods that contributed the most to energy and protein intake were identified. Of these, foods producing the highest GHG emissions were matched with proposed environmentally sustainable alternatives, and their impact on nutrient provision determined. Meats, grains, and dairy products were identified as important sources of energy and protein. With the highest GHG emissions, beef was selected as the reference food. Proposed alternatives included chicken, eggs, fish, tofu, legumes, and nuts. The most pronounced reductions in CO2 emissions were from replacing beef with tofu, legumes, and nuts. Replacing one serve per week of beef with an isocaloric serve of firm tofu during pregnancy could reduce GHG emissions by 372 kg CO2 eq and increase folate (+28.1 µg/serve) and fiber (+3.3 g/serve) intake without compromising iron (+1.1 mg/serve) intake. Small dietary substitutions with environmentally sustainable alternatives can substantially reduce environmental impact without compromising nutrient adequacy.