Molecular dynamics simulations were utilized to investigate the relationship between the structure of paraffins in solid and liquid states and its thermal conductivity. We observe that upon crystallization, a nanocrystalline paraffin structure develops and the value of thermal conductivity doubles, in agreement with experimental data. The introduction of carbon nanotubes or graphene layers leads to liquid ordering and associated thermal conductivity enhancement. More prominently, carbon nanofillers provide a template for directed crystallization and lead to even greater thermal conductivity increases. Our results indicate that introducing carbon nanotubes and graphene into long-chain paraffins leads to a considerable enhancement in thermal conductivity, not only due to the presence of a conductive filler, but also due to the filler-induced alignment of paraffin molecules.