In recent years, non-tuberculous mycobacteria (NTM), once considered merely environmental saprophytes, have emerged as a major cause of opportunistic infections. There is no evidence of human-to-human transmission but they have been found in several environmental water samples. It is, therefore, of the utmost importance to develop methods of rapidly and accurately detecting non-tuberculous mycobacteria in water samples. To obtain a maximum recovery rate and a reduction of Mycobacterium spp. detection time in water samples, different decontamination, enrichment procedures and antibiotics supplements were tested before the inoculation into the Bactec® system. The proposed method of sample treatment (decrease in the decontamination time, followed for a peptone pre-enrichment step and an aztreonam and cefepime supplement) before the inoculation into the Bactec® system proved to be a good option for reliable and fast detection of Mycobacterium spp. in water samples.