Background: We aimed to determine the effectiveness of 4 weeks of balance exercise compared with no intervention on objectively measured postural sway. Methods: This was a single-center parallel randomized controlled, open label, trial. A six-sided dice was used for allocation at a 1:1-ratio between exercise and control. The trial was performed at a university hospital clinic in Sweden and recruited community-dwelling older adults with documented postural instability. The intervention consisted of progressively challenging balance exercise three times per week, during 4 weeks, with follow-up at week five. Main outcome measures were objective postural sway length during eyes open and eyes closed conditions. Results: Sixty-five participants aged 70 years (balance exercise n = 32; no intervention n = 33) were randomized. 14 participants were excluded from analysis because of early dropout before follow-up at week five, leaving 51 (n = 22; n = 29) participants for analysis. No significant differences were detected between the groups in any of the postural sway outcomes. Within-group analyses showed significant improvements in hand grip strength for the intervention group, while Timed Up & Go improvements were comparable between groups but only statistically significant in the control group. Conclusions: Performing balance exercise over a four-week intervention period did not acutely improve postural sway in balance-deficient older adults. The lower limit in duration and frequency to achieve positive effects remains unclear. Trial registration: Clinical trials NCT03227666, July 24, 2017, retrospectively registered.