This paper aims at investigating whether increased regional trade in food staples among the countries of East Africa translates to household welfare gains or not. This is against the backdrop of increased investment by the individual countries and development partners to facilitate easy cross-border flow of food staples to enhance food and nutritional security, and income, especially among the poor households. Our findings show that trade improves child nutrition among households in food deficit areas. Other important factors in explaining child nutritional outcomes include: birth-spacing, age of the household head, mothers’ level of education, ease of access to water, gender of the child, and access to improved toilet facilities. The policy implication of this is that investment in measures that encourage freer regional trade would be a milestone in the right direction towards the realization of food and nutritional security.