Introduction There is an increasing interest in the role of preoperative physical activity for postoperative recovery. The effect of preoperative physical activity and recovery after cholecystectomy is unknown. The aim of this study was to evaluate the association of self-reported leisure-time preoperative physical activity with postoperative recovery and complications after elective cholecystectomy due to gallstone disease. Methods Prospective observational cohort study with 200 patients scheduled to undergo elective cholecystectomy. Level of self-assessed leisure-time physical activity was compared with recovery. Results Regular physical activity was associated with a higher degree of return to work within three weeks post-operatively (relative chance (RC) 1.26, p = 0.040); with a higher chance of leaving hospital within one day post-op (RC 1.23, p = 0.001), as well as with better mental recovery (RC 1.18, p = 0.049), compared to physically inactive. No statistically significant association was seen with return to work within one week or with self-assessed physical recovery. Discussion In clinical practice, evaluating the patients’ level of physical activity is feasible, and may potentially be used to identify patients being more suitable for same-day surgery. Given the study design, the results from this study cannot prove causality. Conclusion The present study shows that the preoperative leisure-time physical activity-level, is positively associated with less sick leave, a shorter hospital stay and with better mental recovery, three weeks post-elective cholecystectomy. We recommend assessing the physical activity-level preoperatively for prognostic reasons. If preoperative/postoperative physical training will increase recovery remains to be shown in a randomized controlled study.