Extremely halophilic archaea are one of the principal microbial community components in hypersaline environments. The majority of cultivated haloarchaea are aerobic heterotrophs using peptides or simple sugars as carbon and energy sources. At the same time, a number of novel metabolic capacities of these extremophiles were discovered recently among which is a capability of growing on insoluble polysaccharides such as cellulose and chitin. Still, polysaccharidolytic strains are in minority among cultivated haloarchaea and their capacities of hydrolyzing recalcitrant polysaccharides are hardly investigated. This includes the mechanisms and enzymes involved in cellulose degradation, which are well studied for bacterial species, while almost unexplored in archaea and haloarchaea in particular. To fill this gap, a comparative genomic analysis of 155 cultivated representatives of halo(natrono)archaea, including seven cellulotrophic strains belonging to the genera Natronobiforma, Natronolimnobius, Natrarchaeobius, Halosimplex, Halomicrobium and Halococcoides was performed. The analysis revealed a number of cellulases, encoded in the genomes of cellulotrophic strains but also in several haloarchaea, for which the capacity to grow on cellulose was not shown. Surprisingly, the cellulases genes, especially of GH5, GH9 and GH12 families, were significantly overrepresented in the cellulotrophic haloarchaea genomes in comparison with other cellulotrophic archaea and even cellulotrophic bacteria. Besides cellulases, the genes for GH10 and GH51 families were also abundant in the genomes of cellulotrophic haloarchaea. These results allowed to propose the genomic patterns, determining the capability of haloarchaea to grow on cellulose. The patterns helped to predict cellulotrophic capacity for several halo(natrono)archaea, and for three of them it was experimentally confirmed. Further genomic search revealed that glucose and cellooligosaccharides import occurred by means of porters and ABC (ATP-binding cassette) transporters. Intracellular glucose oxidation occurred through glycolysis or the semi-phosphorylative Entner-Dudoroff pathway which occurrence was strain-specific. Comparative analysis of CAZymes toolbox and available cultivation-based information allowed proposing two possible strategies used by haloarchaea capable of growing on cellulose: so-called specialists are more effective in degradation of cellulose while generalists are more flexible in nutrient spectra. Besides CAZymes profiles the groups differed in genome sizes, as well as in variability of mechanisms of import and central metabolism of sugars.