Oleogels are a class of solid-fat mimetics that contain a large fraction of oil. Most of these materials have low stiffness and poor oil-binding capacity at commercially viable concentrations, which limits their application in the food and cosmetic industries. To improve their mechanical behavior, we exploited the concepts of particulate-filled materials by developing oil-continuous monoglyceride composites reinforced with crystalline cellulose of various sizes. Cellulose was used as the reinforcing filler material due to its strength, biodegradability, and abundance. The composites gradually stiffened and became more brittle with a progressive increase of the cellulose weight fraction as the maximum packing fraction of fillers approached. This was manifested as an increase in the viscoelastic moduli and yield stress, consistent with the size of the filler. Based on differential scanning calorimetry, X-ray diffraction, X-ray scattering analyses, and microscopic analyses, the inert surface of crystalline celluloses provided a solid substrate for the crystallization of monoglycerides, favoring the lamellar stacking of monoglyceride molecules during the composite oleogel formation regardless of the cellulose size. The present study suggests that cellulose is a suitable bio-based filler material to obtain mechanically strong oleogels suitable for high-shear applications e.g., in food and pharmaceutical industries.