Solid fat is a “staple” in the modern diet in the form of products such as butter, margarine, and shortening. Due to its potentially detrimental effects on health, numerous dietary guidelines recommend its restriction. This opens up opportunities to develop fat replacers via edible oil structuring. In this study, we report the development of a unique, non-thermal method to create oleogels which contain only natural food fibres and liquid vegetable oil. Moreover, they do not oil off on compression. The objective was to understand how the structure of insoluble fibre influenced the physical properties of oleogel, specifically physical robustness and apparent melting point. The fibres studied were citrus fibre of different particle size, and nata de coco fibre known for its thinner dimension and finer three-dimensional structure. Melting characteristics of oleogel were studied by differential scanning calorimetry and visual observation. Physical robustness of oleogel was characterised by the Texture Analyser spreadability method. The presence of fibre was found to disrupt fat crystallisation, leading to proportionately more crystal species that were less stable. However, the true melting point of fat was not significantly altered. Despite greater disruption, oleogels made with longer and/or more extensive fibres were mainly firmer and capable of keeping the oil in solid oleogel form, even under elevated temperatures. Our novel approach to manufacture oleogels opens up a range of opportunities for their application in various products and systems.