Food insecurity is an important social risk factor that is directly linked to patient health and well-being. The Department of Veterans Affairs (VA) aims to identify and resolve food insecurity through social and clinical interventions. However, evaluating the impact of such interventions is made challenging by the lack of follow-up data on Veteran food insecurity status. One potential solution is to leverage documentation of food insecurity in electronic health records (EHRs). In this paper, we developed and validated a natural language processing system to identify food insecurity status from clinical notes and applied it to study longitudinal trajectories of food insecurity among a large cohort of food insecure Veterans. Our analyses provide insight into the timing and persistence of Veteran food insecurity; in the future, our methods will be used to evaluate food insecurity interventions and evaluate VA policy.