Two novel glycoside hydrolases were cloned from the genomic DNA of alklinphilic bacterium Cellulomonas bogoriensis 69B4 and functionally expressed in Escherichia coli. The two enzymes shared less than 73% of identities with other known glycosidases and belonged to glycoside hydrolase families 5 and 9. Recombinant Cel5A exhibited optimum activity at pH 5.0 and at a temperature of 70 °C, and Cel9A showed optimum activity at pH 7.0 and at a temperature of 60 °C. The two enzymes exhibited activity at alkaline pH 11 and were stable over a wide range of pH. The maximum activities of Cel5A and Cel9A were observed in 0.5 M NaCl and 1 M KCl, respectively. In addition, these two enzymes exhibited excellent halostability with residual activities of more than 70% after pre-incubation for 6 days in 5 M NaCl or 4 M KCl. Substrate specificity analysis revealed that Cel5A and Cel9A specifically cleaved the β-1,4-glycosidic linkage in cellulose with the highest activity on carboxymethyl cellulose sodium (78.3 and 145.3 U/mg, respectively). Cel5A is an endoglucanase, whereas Cel9A exhibits endo and exo activities. As alkali-activated, thermo-tolerant, and salt-tolerant cellulases, Cel5A and Cel9A are promising candidates for further research and industrial applications.