In 2007 the country of Rwanda started land reform in Eastern and Northern Provinces with the objective of providing access to land as a means of livelihood to the landless and reducing inequality in landholdings in those regions. Based on theory and empirics, this redistribution is expected to have a positive impact on its beneficiaries particularly on household welfare. To contribute on this important debate, this study investigates the impact of land redistribution on households’ food security. With data collected using household survey in July 2009 in Kayonza District, the study tries to assess the impact by using Dietary Diversity and Children’s Nutritional Status (Stunting, Underweight and Wasted) as proxies of Food Security. The results give evidence to suggest that access to land has increased the number of people with adequate food quantity compared to the period before they received land. In addition, the results give evidence to suggest the improvement in nutrition status of children as the impact of access to land; the number of children underweight decreased even if many of them are still stunted. This situation is not surprising, because within 18 months a child can improve in weight but not really in height. However, among the new landholders there were still an important number of individuals whose food intake fell below their minimum dietary energy requirements. Hence, this study focuses on the complementary policies to make land redistribution an efficient tool for food security.