Frailty in patients after open-heart surgery influences the type and intensity of a cardiac rehabilitation program. The response to tailored exercise training can be different, requiring convenient tools to assess the effectiveness of a training program routinely. The study aims to investigate whether kinematic measures extracted from the acceleration signals can provide information about frailty trajectories during rehabilitation. One hundred patients after open-heart surgery, assigned to the equal-sized intervention and control groups, participated in exercise training during inpatient rehabilitation. After rehabilitation, the intervention group continued exercise training at home, whereas the control group was asked to maintain the usual physical activity regimen. Stride time, cadence, movement vigor, gait asymmetry, Lissajous index, and postural sway were estimated during the clinical walk and stair-climbing tests before and after inpatient rehabilitation as well as after home-based exercise training. Frailty was assessed using the Edmonton frail scale. Most kinematic measures estimated during walking improved after rehabilitation along with the improvement in frailty status, i.e., stride time, cadence, postural sway, and movement vigor improved in 71%, 77%, 81%, and 83% of patients, respectively. Meanwhile, kinematic measures during stair-climbing improved to a lesser extent compared to walking. Home-based exercise training did not result in a notable change in kinematic measures which agrees well with only a negligible deterioration in frailty status. The study demonstrates the feasibility to follow frailty trajectories during inpatient rehabilitation after open-heart surgery based on kinematic measures extracted using a single wearable sensor.