The effectiveness of the use of cellulose fibers as particulates/composite reinforcers involves the assessment of the crystallinity of such fibers. The aim of the present work is to provide information on the degree of crystallinity of the cellulose microfibers obtained from the stems of Cistus ladanifer and Erica arborea shrubs through two different methods, namely an alkaline treatment and a microwave-assisted deep eutectic solvent (DES) method. The crystallinity indexes (CrI) obtained from X-ray powder diffraction patterns indicated that higher CrI were attained for cellulose obtained from the DES treatment. Complementary information on the degree of crystallinity was also retrieved from attenuated total reflection- Fourier transform infrared spectroscopy (ATR-FTIR) vibrational spectra, scanning electron microscopy (SEM) micrographs, and accessibility data for the DES-treated celluloses from the two species. The crystallinity results for the fibers derived from these two Mediterranean shrubs were within the range of the results for those derived from wood pulp, opening the door to their valorization for cellulose-derived packing applications or for their use as reinforcers in composite materials in combination with other biopolymers.