The broad objective of this study is to highlight key constraints, opportunities and challenges relating to interventions aimed at strengthening the nutrition security of people living with HIV who are on antiretroviral (ARV) treatment. The research took place under the auspices of the Academic Model for Prevention and Treatment of HIV/AIDS (AMPATH). AMPATH cares for over 27,000 people living with HIV and AIDS (PLWHA) in western Kenya, of which just over fifty percent are on ARV treatment. A short-term nutrition intervention linked to the provision of free ARV treatment was initiated in 2002. Viewing this intervention from a broader perspective of nutrition security, the paper identifies programmatic lessons and challenges to linking nutritional and other comprehensive support services with ARV treatment in a resource poor setting. Qualitative research was conducted between December 2005 and early 2006. Twenty key informant interviews, 9 focus group discussions, and 79 in-depth interviews were undertaken with a sample of patients who have either participated or not participated in the food program. Lessons learned include the following: The intervention provides an important source of food support to the most vulnerable patients on treatment and their households, contributes to greater dietary diversity, and plays an important role in the emotional well-being of clients by lowering stress caused by insufficient access to food. Many patients in the supplementation program also self-report recovery of physical strength that allowed them to return to productive life and greater adherence to treatment. Observable improvements in patients’ nutritional and health status acted as a catalyst for increased support from family and community. The main opportunity costs of participation in the program are transport and stigma associated with collection of food supplements. The implementation of enrollment criteria has posed many challenges to program staff, particularly in determining eligibility of cases that fall near enrollment guideline cut-offs.