Much effort has been devoted to defining healthy diets, which could lower the burden of disease and provide targets for populations. However, these target diets are far removed from current diets, so at best, the population is expected to move slowly along a trajectory. Our aim was to characterize the different possible trajectories toward a target diet and identify the most efficient one for health to point out the first dietary changes being the most urgent to implement. Using grah theory, we have developed a new method to represent in a graph all stepwise change trajectories toward a target healthy diet, with trajectories all avoiding risk of nutrient deficiency. Then, we have identified and characterized the trajectory with the highest value for long-term health. Observed male and female average diets are from the French representative survey INCA3, and target diets were set using multicriteria optimization. The best trajectories were found using the Dijkstra algorithm with the Health risk criteria based on epidemiological data. Within ∼2.6M diets in the graphs, we found optimal trajectories that were rather similar for males and females regarding the most efficient changes in the first phase of the pathways. In particular, we found that a 1-step increase in the consumption of whole/semirefined bread (60 g) was the first step in all healthiest trajectories. In males, the subsequent decrease in red meat was immediately preceded by increases in legumes. We show simple practical dietary changes that can be prioritized along an integral pathway that is the most efficient overall for health when transiting toward a distant healthy diet. We put forward a new method to analyze dietary strategy for public health transition and highlight the first critical steps to prioritize.