The present work was carried out to isolate the cellulose-decomposing bacteria (CDB) from Wadi El-Natron, Egypt. Totally 40 isolates were isolated from saline mud samples. Eight out of 40 isolates exhibited high hydrolysis capacity of the Congo-Red screening method. The highly producer isolate (CDB2) was selected to optimize some nutritional and environmental factors for improving cellulase production. The bacterial isolate was identified on the basis of molecular characteristics using 16srRNA. The sequence analysis showed 99% similarity to Brevibacterium halotolerans, which is then deposited in the GenBank in NCBI under the accession number MN148622. The bacterium showed highly cellulase production by using carboxymethyl cellulose (CMC) as a sole carbon source. The results showed that the optimum conditions for cellulase production by the selected isolate were noticed when grown on CMC (20 g/L) at pH 8.0 incubated at 35οC in batch conditions with shaking. The results revealed that, the bacterial isolate showed potential cellulase production at stationary phase of growth corresponding to an incubation period of 3-5 days. The cellulase enzyme has high specificity to CMC considered to be an endo-1,4-glucanase.