Background Health care utilization after coronary artery bypass graft (CABG) surgery is high and is partly of an unplanned nature. eHealth applications have been proposed to reduce care consumption, which involve and assist patients in their recovery. In this way, health care expenses could be reduced and quality of care could be improved. Objective The aim of this study was to evaluate if an eHealth program can reduce unplanned health care utilization and improve mental and physical health in the first 6 weeks after CABG surgery. Methods A single-blind randomized controlled trial was performed, in which patients scheduled for nonacute CABG surgery were included from a single center in the Netherlands between February 2020 and October 2021. Participants in the intervention group had, alongside standard care, access to an eHealth program consisting of online education videos and video consultations developed in conjunction with the Dutch Heart Foundation. The control group received standard care. The primary outcome was the volume and costs of a composite of unplanned health care utilization, including emergency department visits, outpatient clinic visits, rehospitalization, patient-initiated telephone consultations, and visits to a general practitioner, measured using the Medical Technology Assessment Medical Consumption Questionnaire. Patient-reported anxiety and recovery were also assessed. Intention-to-treat and “users-only” analyses were used. Results During the study period, 280 patients were enrolled and randomly allocated at a 1:1 ratio to the intervention or control group. The intention-to-treat analysis consisted of 136 and 135 patients in the intervention and control group, respectively. At 6 weeks, the primary endpoint had occurred in 43 of 136 (31.6%) patients in the intervention group and in 61 of 135 (45.2%) patients in the control group (hazard ratio 0.56, 95% CI 0.34-0.92). Recovery was faster in the intervention group, whereas anxiety was similar between study groups. “Users-only” analysis yielded similar results. Conclusions An eHealth strategy comprising educational videos and video consultations can reduce unplanned health care utilization and can aid in faster patient-reported recovery in patients following CABG surgery. Trial Registration Netherlands Trial Registry NL8510; https://trialsearch.who.int/Trial2.aspx?TrialID=NL8510 International Registered Report Identifier (IRRID) RR2-10.1007/s12471-020-01508-9