Objective To evaluate the impact of Teach-Back on communication quality in a national telephonebased telehealth service, for callers varying in health literacy. Design Cross-sectional stepped wedge cluster randomised trial with continuous recruitment, short (fixed) exposure and blinded outcome assessors. Nurses were stratified by hours worked and randomised into training groups using a computer generated sequence. Setting An Australian national pregnancy and parenting telephone helpline. Intervention Complex intervention involving a single 2-hour group Teach-Back training session, combined with ongoing nurse self-reflection on their communication following each call and each shift. Participants Participants were 637 callers to the telephone helpline aged 18-75 (87% female), of whom 127 (13%) had inadequate health literacy (measured with the Single Item Literacy Screener); and 15 maternal and child health nurses with 15 years' experience on average. Measures Primary outcome was a modified subscale of the Health Literacy Questionnaire, 'having sufficient information to manage health'. Secondary caller outcomes included caller confidence, perceived actionability of information and nurse effort to listen and understand. Nurse outcomes were perceptions of their communication effectiveness. Results Over a 7 week period, 376 surveyed callers received usual care and 261 Teach-Back. Ratings on the primary outcome increased over time (OR 1.17, CI 1.01 to 1.32, p = 0.03) but no independent Teach-Back effect was observed. A consistent pattern suggests that, compared with usual care, Teach-Back helps callers with inadequate health literacy feel listened to (OR 2.3, CI 0.98 to 5.42, p = 0.06), confident to act (OR 2.44, CI 1.00 to 5.98, p = 0.06), and know what steps to take (OR 2.68, CI 1.00 to 7.17, p = 0.06). Nurse perceptions of both their own communication effectiveness (OR = 2.31; CI 1.38 to 3.86, p<0.0001), and caller understanding (OR = 2.56; CI 1.52 to 4.30, p<0.001) both increased with Teach-Back. No harms were reported. Conclusions Teach-Back appears to benefit telephone health service users with inadequate health literacy, but the extent of this is unclear due to smaller numbers of lower literacy participants. Improving caller ratings over time are likely due to increasing nurse communication competence.