Abstract Background Pragmatic randomized clinical trials are essential to determine the effectiveness of interventions in “real-world” clinical practice. These trials frequently use a cluster-randomized methodology, with randomization at the site level. Despite policymakers’ increased interest in supporting pragmatic randomized clinical trials, no studies to date have reported on the unique recruitment challenges faced by cluster-randomized pragmatic trials. We investigated key challenges and successful strategies for hospital recruitment in the Comprehensive Post-Acute Stroke Services (COMPASS) study. Methods The COMPASS study is designed to compare the effectiveness of the COMPASS model versus usual care in improving functional outcomes, reducing the numbers of hospital readmissions, and reducing caregiver strain for patients discharged home after stroke or transient ischemic attack. This model integrates early supported discharge planning with transitional care management, including nurse-led follow-up phone calls after 2, 30, and 60 days and an in-person clinic visit at 7–14 days involving a functional assessment and neurological examination. We present descriptive statistics of the characteristics of successfully recruited hospitals compared with all eligible hospitals, reasons for non-participation, and effective recruitment strategies. Results We successfully recruited 41 (43%) of 95 eligible North Carolina hospitals. Leading, non-exclusive reasons for non-participation included: insufficient staff or financial resources (n = 33, 61%), lack of health system support (n = 16, 30%), and lack of support of individual decision-makers (n = 11, 20%). Successful recruitment strategies included: building and nurturing relationships, engaging team members and community partners with a diverse skill mix, identifying gatekeepers, finding mutually beneficial solutions, having a central institutional review board, sharing published pilot data, and integrating contracts and review board administrators. Conclusions Although we incorporated strategies based on the best available evidence at the outset of the study, hospital recruitment required three times as much time and considerably more staff than anticipated. To reach our goal, we tailored strategies to individuals, hospitals, and health systems. Successful recruitment of a sufficient number and representative mix of hospitals requires considerable preparation, planning, and flexibility. Strategies presented here may assist future trial organizers in implementing cluster-randomized pragmatic trials. Trial registration Clinicaltrials.gov, NCT02588664. Registered on 23 October 2015.