Background: Isolation of mycobacteria from the sputum of patients with cystic fibrosis (CF) is challenging due to the overgrowth of cultures by other bacteria and fungi. In this setting, Burkholderia cepacia selective agar (BCSA) has been recommended as a convenient and effective culture medium for the isolation of rapidly-growing, non-tuberculous mycobacteria (NTM). A novel selective culture medium (RGM medium) was evaluated for the isolation of rapidly-growing NTM from the sputum of children and adults with CF. Methods: A total of 118 isolates of rapidly-growing mycobacteria and 98 other bacteria and fungi were inoculated onto RGM medium. These were assessed for growth at 30 °C over a seven day period. A total of 502 consecutive sputum samples were collected from 210 patients with CF. Each sample was homogenized and cultured onto RGM medium and also onto BCSA. Cultures were incubated for 10 days at 30 °C. Results: Of 118 isolates of mycobacteria all but one grew well on RGM medium, whereas 94% of other bacteria and fungi were inhibited. A total of 55 sputum samples (from 33 distinct patients) yielded NTM using a combination of both RGM and BCSA (prevalence: 15.7%). NTM were recovered from 54 sputum samples using RGM medium compared with only 17 samples using BCSA (sensitivity 98% vs. 31%; P ≤ 0.0001). A total of 419 isolates of non-mycobacteria were recovered from sputum samples on BCSA compared with 46 on RGM medium. Conclusions: RGM medium offers a simple and effective culture method for the isolation of rapidly-growing mycobacteria from sputum samples from patients with CF without decontamination of samples. RGM medium allows for the systematic screening of all sputum samples routinely referred for culture from patients with CF.