There are currently no longitudinal studies of cognitive performance in older patients with Posttraumatic Stress Disorder (PTSD). It is therefore unclear whether relationships between memory and symptoms differ over time among older persons with and without PTSD. Twenty-eight Holocaust survivors and nineteen comparison subjects were evaluated 5 years after they had received a memory assessment including paired-associates learning and the California Verbal Learning Test (CVLT). While Holocaust survivors with PTSD showed a diminution in symptom severity (t = 2.99, df = 12, p = .011), they still manifested a decline in paired associates learning, suggesting an acceleration in age-related memory impairment (related word pairs: t = 2.87, df = 13, p = .013; unrelated word pairs: t = 2.06, df = 13, p = .060). The survivors with PTSD showed improvements on several CVLT measures over time. These improvements correlated with symptom improvements, such that group differences at the follow-up were no longer detected. The discrepancy in the pattern of performance on these two tests of memory following symptom improvement suggests possible differentiation between of aspects of memory functions associated with aging and trauma exposure and those associated with the severity of PTSD symptoms. Performance on the CVLT appeared related to clinical symptom severity while paired associate learning worsened over time in Holocaust survivors with PTSD, consistent with earlier cross-sectional findings.