The manufacture of nanocomposite materials based on polyolefins and paraffins is a promising approach for developing materials with enhanced performance characteristics for a wide range of applications. However, a more profound understanding is required to identify how the material properties depend on the type of filler and its concentration, as well as on the structure of the composite matrix. In this study, the effect of adding several types of polycyclic aromatic hydrocarbons (PAH) with different molecular sizes-coronene, ovalene, and hexabenzocoronene (HBC) at concentrations ranging from 10 to 40 wt%-to composites based on polyethylene (PE) or paraffin was studied using all-atomistic computer simulation. Our study revealed how the size of the PAH molecules influences their aggregate behavior, phase transitions, and the structure of the composite matrix. It was shown that coronene exhibits weak aggregation in paraffin and prevents its crystallization, which results in a pronounced decrease in the crystallization temperature of both PE and paraffin in the composites. Ovalene and HBC demonstrate a stronger tendency to aggregate, forming substantially larger aggregates than coronene. Both these PAHs increase the crystallization temperature of PE or paraffin in the composites. At the same time, up to a certain concentration, ovalene can integrate into the paraffin crystal structure at low temperature, promoting its crystallization. In contrast, HBC forms extended columnar aggregates at both high and low temperatures, creating steric hindrances to the formation of the crystalline matrix structure and ultimately reducing the degree of crystallinity of PE or paraffin in the composites. Thus, by adding aromatic nanofillers, it becomes possible to control the microstructure and phase behavior of polyolefin-based composites.