“The Nordic diet” is an umbrella term that encompasses any interpretation that combines Food-Based Dietary Guidelines (FBDGs) with local Nordic foods. The five Nordic countries have collaborated on Nordic Nutrition Recommendations for forty years, including FBDGs, so their national guidelines are similar. The countries also share similar public health issues, including widespread nonconformity to the guidelines, although in different ways. The aim of this concept paper is to discuss environmental sustainability aspects of the Nordic diet, describe the status of and make suggestions for the inclusion of sustainability in future work on the Nordic diet. We exploit the sustainability–health synergy. A food intake more in line with the current FBDGs, which emphasises more plant-based and less animal-based foods, is necessary for high environmental sustainability. In turn, sustainability is an important motivator for health-promoting dietary shifts. Policy development requires long-term efforts. Since the Nordic diet can be considered a further development and improvement of old, traditional diets, there is huge potential to formulate a Nordic diet that benefits both human and planetary health. It is time for concerted engagement and actions—a new Nordic nutrition transition.