The cold-flow properties of hydrotreated vegetable oils (HVO) and their blends with petroleum diesel were investigated by solid-state NMR (SSNMR). The fraction of protons in the crystallites was successfully determined at temperatures going from 30 °C to −50 °C, offering a way to precisely monitor the crystallization process occurring during the cool-down of hydrocarbons. The Magic Sandwich Echo experiment used in this work displayed a higher sensitivity compared to other methods such as cloud point, pour point, and cold filter plugging points, with a detection of the onset of crystallization by SSNMR up to 15 °C with respect to other techniques. The properties of three distinct HVO and of their blends with petroleum diesel were determined and related to their detailed chemical composition. Results showed that a high branching level was the primary factor impacting the onset of crystallization of the HVO. The carbon number distribution was observed to impact the rate of crystallization as a function of the temperature. Lastly, blending petroleum diesel with HVO was demonstrated to keep the cold-flow properties of the diesel unchanged at 10 wt % mixing. In contrast, a shift of the cold-flow properties of the blends toward the HVO behavior was detected at 30 and 50 wt % mixing, with either a negative or positive impact depending on the chemical composition of the added HVO.