Cellulose nanocrystal (CNC)-based composite films were prepared as a solid electrolyte for alkaline fuel cells. Poly(vinyl alcohol) (PVA) and silica gel hybrid were used to bind the CNCs to form a robust composite film. The mass ratio (i.e., 1 : 1, 1 : 2) of PVA and silica gel was tuned to control the hydrophobicity of the resulting films. Composite films with a range of CNC contents (i.e., 20–60%) were prepared to demonstrate the impact of CNCs on the performance of these materials as a solid electrolyte for alkaline fuel cells. Different from previously reported cross-linked polymer films, CNC-based composite films with 40% hydrophobic binder (i.e., PVA : silica gel = 1 : 2) exhibited simultaneous low water swelling (e.g., ∼5%) and high water uptake (e.g., ∼80%) due to the hydrophilicity and extraordinary dimensional stability of CNCs. It also showed a conductivity of 0.044 and 0.065 S cm⁻¹ at 20 and 60 °C, respectively. To the best of our knowledge, the film with 60% CNC and 40% binder is characterized by the lowest hydroxide conductivity-normalized swelling ratio. Decreased CNC contents (i.e., 40 and 20%) resulted in comparable hydroxide conductivity but a greater swelling ratio. These results demonstrate the advantage of CNCs as a key component for a solid electrolyte for alkaline fuel cells over conventional polymers, suggesting the great potential of CNCs in improving the dimensional stability while maintaining the conductivity of existing anion exchange membranes.