CONTEXT: Despite recent improvements in living standards, a substantial proportion of farm households in sub-Saharan Africa (SSA) is food insecure, and increasing crop productivity could help address this problem. OBJECTIVE: We estimated the effect of increasing maize yields with mineral fertilizer on household food security and on regional and national maize supply in two East African countries - Uganda and Tanzania. METHODS: We estimated maize yield response to nitrogen (N) fertilization with a machine learning model trained on 15,952 observations of maize responses to fertilizer across SSA. Together with spatial price data, we used this model to quantify the profit-maximizing N fertilizer input for a nationally-representative sample of 4188 agricultural households in the two countries. We computed a food availability indicator for all households. RESULTS AND CONCLUSIONS: The mean profit-maximizing N input was 82 kg/ha in Tanzania, but it was much lower in Uganda (24 kg/ha) mostly because of less favorable prices. The profit-maximizing N input was above the reported N input for 95% of the households in Tanzania and for 43% of the households in Uganda. It was predicted to increase the food availability ratio of food insecure maize growers by 95% in Tanzania, and by 25% in Uganda. The administrative regions where maize supply could increase most were not the same as the regions where the increase in household-level food security was largest. With increased fertilization, food insecure maize growing households (35% in Tanzania and 42% in Uganda) could only contribute about 20% of the overall increase in maize supply, whereas the 20 to 30% food secure households that have a larger area planted with maize could contribute >60%. SIGNIFICANCE: Our study makes two key contributions: i) a substantial increase in national maize supply is more likely to come from already food secure households with relatively large farms, while food insecure households with small farms may n