Oleofoams have attracted great interest for many personal care applications due to their favorable physicochemical properties, including texture and detergency. To explore the potential use of mixtures of high-melting fat crystals [tribehenoyl-glycerol (BBB)] and edible oils as low-cost and stable aeration systems, we created oleofoams composed of olive oil and BBB. By whipping BBB/olive oil oleogels following rapid cooling and subsequent heating, we succeeded in preparing oleofoams without emulsifier additives. The mixtures of BBB/olive oil formed oleofoams at BBB concentrations of 4.0–20.0 wt.%. The resultant oleofoams maintained their overrun rates and did not coalescence, even with additional whipping after the overrun rate was maximized. More tightly arranged bubbles and concentrated bubble size distributions, as well as stronger interfacial elasticity, were attributed to increasing BBB concentrations, and thermal results revealed that more heating was required to damage the foam structure. The characteristics of these new oleofoams were closely related to their BBB concentrations, and observed effects were attributed to the network structure of the thickened crystal layer and enhanced gelling in the oil phase.