Objectives: To evaluate the efficacy of a brief tailored non-pharmacological intervention comprising breathing retraining and psychosocial support for managing dyspnea in cancer patients. Design: Multicenter, single blinded, parallel group, randomized controlled trial. Setting: Four major public hospitals, Brisbane, Australia. Participants: One hundred and forty four cancer patients, including 81 who received an 8-week tailored intervention and 63 who received standard care. Inclusion Criteria: Diagnosis of small or non-small cell lung cancer, mesothelioma or lung metastases; completed first line therapy for the disease; average dyspnea rating >2 on (0–10) rating scale in past week; anticipated life expectancy ≥3 months. Outcomes: The primary outcome measure was change in “worst” dyspnea at 8 weeks compared to baseline. Secondary outcomes were change in: dyspnea “at best” and “on average”; distress; perceived control over dyspnea; functional status, psychological distress; and use of non-pharmacological interventions to manage dyspnea at 8 weeks relative to baseline. Results: The mean age of participants was 67.9 (SD = 9.6) years. Compared to the control group, the intervention group demonstrated a statistically significant: (i) improvement in average dyspnea from T1(M = 4.5, SE = 0.22) to T3 (M = 3.6, SE = 0.24) vs. (M = 3.8, SE = 0.24) to (M = 4.1, SE = 0.26); (ii) greater control over dyspnea from T1 (M = 5.7, SE = 0.28) to T3 (M = 7.5, SE = 0.31) vs. (M = 6.8, SE = 0.32) to (M = 6.6, SE = 0.33); and (iii) greater reduction in anxiety from T1 (M = 5.4, SE = 0.43) to T3 (M = 4.5, SE = 0.45) vs. (M = 4.2, SE = 0.49) to (M = 4.6, SE = 0.50). This study found no intervention effect for best and worst dyspnea, distress from breathlessness, functional status, and depression over time. Conclusions: This study demonstrates efficacy of tailored non-pharmacological interventions in improving dyspnea on average, control over dyspnea, and anxiety for cancer patients. Clinical Trial Registration: The trial is registered at the Australian New Zealand Clinical Trials Registry (http://www.anzctr.org.au). The registration number is ACTRN12607000087459.