The effects of chemical and enzymatic interesterification on the structure and rheological behavior of blends of fully hydrogenated canola oil (FHCO) with high oleic acid sunflower oil in the range of 10–90% was studied. Relationships between chemical composition, crystallization temperature (20–50°C), solid fat content (SFC) of the blends, and their rheological properties, characterized using both small and large deformation mechanical testing, were investigated. The storage modulus (G′) and yield force increased with FHCO concentration in the blends and was affected strongly by interesterification. The SFC in the interesterified samples was lower than in the non-interesterified blends, but they had higher values of G′. This increase in G′ at 30°C upon interesterification was attributed to a decrease in the fractal dimension of the fat crystal network which translates into a decrease in crystal cluster size in the interesterified samples. The higher G′ in the chemically interesterified samples relative to the enzymatic interesterified samples, on the other hand, was due to a higher λ parameter which is directly proportional to the strength of interparticle interactions and inversely proportional to crystal size. Microscopy and nucleation kinetics studies allowed for the independent determination of λ.