Objective: Memory problems are commonly reported following stroke; however, the specific nature and frequency of memory complaints experienced by stroke survivors has not been sufficiently investigated. We aimed to investigate the factor structure of the Everyday Memory Questionnaire-Revised (EMQ-R) in stroke survivors with memory complaints, and identify the most commonly endorsed items. Method: A total of 91 stroke survivors completed the EMQ-R prior to participation in a memory rehabilitation trial. A principal components analysis was carried out on the EMQ-R data and reliability analyses were conducted on the resulting subscales. We described the average frequency of occurrence of specific memory complaints in one month, as reported by stroke survivors. Results: The factor analysis yielded a two-component solution which accounted for 60.12% of the variance, suggesting that two subscales termed Forgetting and Attention would be most appropriate for clinical use with stroke survivors. These subscales demonstrated strong internal reliability. A total of 87.9% of the participants reported having word-finding difficulties more than once monthly. Of all EMQ-R items, participants rated word-finding problems as occurring at the highest frequency (once or more daily). Conclusions: Stroke survivors’ everyday memory complaints fall into two distinct categories relating to memory and attentional processes. Calculating scores on the two EMQ-R subscales separately may assist clinicians to understand the nature of memory complaints reported by stroke survivors who participate in memory rehabilitation programs, and may enable more targeted outcome measurement in research trials.