In this work, extra-virgin olive oil (EVO)- and sunflower oil (SFO)-based oleogels were structured using rice bran wax (RBW) at 10% by weight (w/w). Bamboo fiber milled with 40 (BF₄₀), 90 (BF₉₀) and 150 (BF₁₅₀) µm of average size was added as a structuring agent. The effect of fiber addition and cooling temperature (0, 4, and 25 °C) on thermal and structural parameters of achieved gels was assessed by rheological (both in rotational and oscillatory mode), texture, and differential scanning calorimetry tests. Oleogelation modified the rheological behavior of EVO and SFO, thus shifting from a Newtonian trend typical of oils to a pseudoplastic non-Newtonian behavior in gels. Moreover, oleogels behaved as solid-like systems with G′ > G″, regardless of the applied condition. All samples exhibit a thermal-reversible behavior, even though the presence of hysteresis suggests a partial reduction in structural properties under stress. Decreasing in cooling temperature negatively contributed to network formation, despite being partially recovered by low-granulometry fiber addition. The latter dramatically improved either textural, rheological, or stability parameters of gels, as compared with only edible oil-based systems. Finally, wax/gel compatibility affected the crystallization enthalpy and final product stability (gel strength) due to different gelator–gelator and gelator–solvent interactions.