During adolescence, many young people gain greater food choice agency but also become increasingly exposed and susceptible to environmental pressures that influence their food choices. This coincides with increased nutritional needs, especially for girls. In urban Colombia, adolescent diets are often high in undesirable foods and low in nutritious foods, contributing to overweight and micronutrient deficiencies. This study aimed to explore the potential of improving diet quality using food-based recommendations (FBRs) within the parameters of local food systems and adolescents' existing dietary patterns to inform context-specific programmatic responses to malnutrition. We applied linear programming analysis to dietary data from 13- to 20-year-old girls in Medellin to identify problem nutrients, local micronutrient sources, and promising FBRs. Iron and, to a lesser extent, calcium targets were difficult to meet using optimized diets based on local foods, especially for 13- to 17-year-olds. High habitual consumption of foods with excessive salt, fat, or sugar provided >5% of micronutrients in optimized diets. Otherwise, significant micronutrient sources included legumes, meat, dairy, bread, potatoes, and fruit. FBRs met targets for 10 micronutrients but only 32%-39% recommended nutrient intake for iron. FBRs, including occasionally consumed foods and supplements, met all intake targets for less cost, indicating a need to increase access to nutrient-dense products.