There is a paucity of information on the incidence and survival of Mycobacterium avium subsp. paratuberculosis (Map) in cheese. The presence of a starter and non-starter microflora may present difficulties for the detection of Map during cheese ripening. Several culture media were evaluated for the detection of Map in Cheddar cheese manufactured with different starter cultures. Serial dilutions of four commercially used Cheddar starter cultures - R603, R604, YY80 and EZAL MM101 were either subjected to a decontamination step (0.75% w/v hexadecylpyridinium chloride (HPC), 5 h at 18ºC) before inoculation onto test media or inoculated directly onto test media. The test media used were: Herrold's Egg Yolk Medium (HEYM) with and without antibiotics (vancomycin (V), amphotericin B (A) and nalidixic acid (N)); Middlebrook 7H10-PANTA agar and BACTEC 12B radiometric medium. In addition, triplicate samples of 10-wk old commercially prepared cheddar cheese made with each starter and laboratory-prepared Cheddar, manufactured with starter YY80 (10-wk) and EZAL MM101 (10-wk and 14-mth), were inoculated (without decontamination) onto the same test media. Without a decontamination step, growth of each starter, except EZAL MM101, occurred on HEYM without antibiotics but not on any of the other media, so inclusion of antibiotics (VAN or PANTA) in media may suppress Cheddar cheese starter cultures sufficiently so as to eliminate a decontamination step. In commercially and laboratory prepared cheeses growth was observed on HEYM-VAN medium for cheese prepared with all starters except EZAL MM101. Therefore HEYM-VAN may not be a suitable medium for the isolation/detection of Map from Cheddar cheese prepared under uncontrolled microbiological conditions. The medium 7H10-PANTA did not support the growth of Cheddar cheese microflora when cheese was prepared with any of the starter cultures. Therefore, in order to monitor the persistence of Map during Cheddar manufacture and ripening the use of 7H10-PANTA medium is recommended.