Cellulose represents the most abundant component of plant biomass on earth; it is degraded by cellulases, specific enzymes produced by microorganisms. However, cellulases of bacterial origin attract more interest due to their natural diversity and ability to inhabit a variety of niches, allowing the selection of cellulolytic strains resistant to environmental stresses. The screening of the cellulolytic activity of 398 bacteria isolated from various ecosystems in Algeria (cave, ruins, chott, thermal station, and rhizosphere of arid and semi-arid regions) was performed by the appearance of a hydrolysis zone on carboxymethylcellulose (CMC) medium. The cellulase activity on CMC (1%) broth allowed to select 26 strains among which 12 had the best activity (0.3 U/mL to 2.2 U/mL). Optimization of physicochemical parameters (salinity: 0–1 M NaCl; pH: 3, 4, 7, 9, and 11; temperature: 30, 45, and 50 °C; PEG8000: 0 and 30%) involved in growth and cellulose production showed that the majority of strains were mesophilic, neutrophilic, or alkali- tolerant and tolerant to 30% of PEG8000. The cellulase activity and stability under different stress allowed to retain five strains, which the most efficient. Based on the 16S-rRNA sequencing results, they belonged to the genus Bacillus. The physicochemical properties of cellulases (crude extract) showed a CMCase active over a wide range of pH (4 to 11), optimal at 50 °C and 60 °C. The inhibiting salinity effect on the activity was not detected and was negligible on the enzymatic stability. The residual CMCase activity remained between 40 and 70% in a temperature range between 40 and 70 °C, was stable over a wide range of saline concentrations (0–2000 mM), and was weakly affected at 30% of PEG8000. The crude enzyme extract was able to hydrolyze both soluble and insoluble cellulosic substrates. The evaluation of the hydrolysis capacity of lignocellulosic waste revealed the ability of tested strains to degrade wheat bran, barley bran, and corncob. In addition, the enzyme showed significant multi-stress resistance on solid and liquid media. By these characteristics, these cellulolytic bacteria could be attractive to be used in various industrial and biotechnology applications.