(1) Objective: This study examined the effects of a combined intervention of Brainastic computerized cognitive training (CCT) preceded by physical exercise (PE) for improving frailty status and cognitive function in older adults. (2) Methods: Older adults aged 50 years or older attending elderly centers, without frailty/history of cognitive impairment, were randomly allocated into either a 12-week (i) multi-domain CCT + PE ( n = 117), (ii) two-domain CCT + PE ( n = 116) or (iii) video watching + PE (i.e., control, n = 114). Brainastic is an online application for cognitive training through video games. The multi-domain CCT targeted memory, attention, executive function, flexibility and visuospatial ability while the two-domain CCT targeted memory and attention. PE included both aerobic and resistance exercises. Outcomes were changes in frailty levels as measured with a simple frailty questionnaire (FRAIL), global cognition as measured with the Rapid Cognitive Screen (RCS), total learning and verbal memory abilities as measured with the Hong Kong List Learning Test (HKLLT), and executive functions as measured with the Frontal Assessment Battery (FAB) over 12 weeks. (3) Results: Participants in the intervention groups (multi-/two-domain CCT + PE) showed greater improvements in frailty status, total learning ability and verbal memory ability than control participants (all p < 0.05). The multi-domain CCT did not outperform the two-domain CCT in improving frailty status or cognitive function. The training effects were independent of the baseline cognition of the participants. (4) Conclusions: A combined intervention of multi-/two-domain CCT preceded by PE seemed to convey benefit over video watching preceded by PE in improving frailty status and cognitive function among older adults attending elderly centers.