The aim of the NavMem project is to develop a mobile navigation companion for elderly persons with memory decline (MCI). The project is intended for a wide range of target users-e.g. persons with memory problems due to early dementia, stroke but also elderly persons in general. In the following we report results from studies made together with the Swedish Stroke Association. We describe the early stages of the user centered design process and provide a list of requirements. We also provide initial designs and early prototypes and report preliminary results from recent user tests.