BACKGROUND: There is a high prevalence of gait impairments in individuals with dementia (IWD). Gait impairments are associated with increased risk of falls, disability, and economic burden for health care systems. Only few studies have investigated the effectiveness of physical activity on gait performance in IWD, reporting promising but inconsistent results. Thus, this study aimed to investigate the effectiveness of a multimodal exercise program (MEP) on gait performance in IWD. METHODS: In this parallel-group randomized controlled trial, we enrolled 319 IWD of mild to moderate severity, living in care facilities, aged ≥ 65 years, and being able to walk at least 10 m. The control group (n = 118) received conventional treatment, whereas the intervention group (n = 201) additionally participated in a 16-week MEP specifically tailored to IWD. We examined the effects of the MEP on spatiotemporal gait parameters and dual task costs by using the gait analysis system GAITRite. Additionally, we compared characteristics between positive, non-, and negative responders, and investigated the impact of changes in underlying motor and cognitive performance in the intervention group by conducting multiple regression analyses. RESULTS: Two-factor analyses of variance with repeated measurements did not reveal any statistically significant time*group effects on either spatiotemporal gait parameters or dual task costs. Differences in baseline gait performance, mobility, lower limb strength, and severity of cognitive impairments were observed between positive, non-, and negative responders. Positive responders were characterized by lower motor performance compared to negative and non-responders, while non-responders showed better cognitive performance than negative responders. Changes in lower limb strength and function, mobility, executive function, attention, and working memory explained up to 39.4% of the variance of changes in gait performance. CONCLUSIONS: The effectiveness of a standardized MEP on gait performance in IWD was limited, probably due to insufficient intensity and amount of specific walking tasks as well as the large heterogeneity of the sample. However, additional analyses revealed prerequisites of individual characteristics and impacts of changes in underlying motor and cognitive performance. Considering such factors may improve the effectiveness of a physical activity intervention among IWD. TRIAL REGISTRATION: DRKS00010538 (German Clinical Trial Register, date of registration: 01 June 2016, retrospectively registered, https://www.drks.de/drks_web/setLocale_EN.do ).