The key material for bioethanol production is cellulose, which is one of the main components of the plant cell wall. Enzymatic depolymerization of cellulose is an essential step in bioethanol production, and can be accomplished by fungal and bacterial cellulases. Most of the biochemically characterized bacterial cellulases come from only a few cellulose-degrading bacteria, thus limiting our knowledge of a range of cellulolytic activities that exist in nature. The recent explosion of genomic data offers a unique opportunity to search for novel cellulolytic activities; however, the absence of clear understanding of structural and functional features that are important for reliable computational identification of cellulases precludes their exploration in the genomic datasets. Here, we explore the diversity of cellulases and propose a genomic approach to overcome this bottleneck.