Background: Hospitalization-associated disability (HAD) is associated with prolonged functional decline and increased mortality after discharge. Therefore, we examined the incidence and risk factors associated with HAD in elderly patients undergoing cardiac surgery in Japan. Methods and Results: We retrospectively examined 2,262 elderly patients who underwent elective cardiac surgery at Sakakibara Heart Institute. HAD was defined as a functional decline between time of admission and discharge measured by the Barthel Index. We analyzed clinical characteristics using machine learning algorithms to identify the risk factors associated with HAD. After excluding 203 patients, 2,059 patients remained, of whom 108 (5.2%) developed HAD after cardiac surgery. The risk factors identified were age, serum albumin concentration, estimated glomerular filtration rate, Revised Hasegawa's Dementia Scale, N-terminal pro B-type natriuretic peptide, vital capacity, preoperative Short Physical Performance Battery (SPPB) score, operation times, cardiopulmonary bypass times, ventilator times, length of postoperative intensive care unit stay, and postoperative ambulation start day. The highest incidence of HAD was found in patients with an SPPB score ≤9 and in those who started ambulation >6 days after surgery (76.9%). Conclusions: Several risk factors for HAD are components of frailty, suggesting that preoperative rehabilitation to reduce the risk of HAD is feasible. Furthermore, the association between HAD and a delayed start of ambulation reaffirms the importance of early mobilization and rehabilitation.