Polyethylene based composites modified with multi-walled carbon nanotubes (MWCNTs) were produced via in situ polymerization of ethylene with the Ti-Ziegler–Natta catalyst preliminarily immobilized on MWCNTs. The composite structure was characterized with transmission and scanning electron microscopy, differential scanning calorimetry (DSC) and in situ synchrotron X-ray Diffraction (in situ XRD). For the first time the Ti-containing catalyst species of the size 2–3 nm were observed on the MWСNTs surface stabilized in the polymer matrix. A comparative study of the melting-crystallization cycles of neat polyethylene (PE) and MWCNT-PE composites with in situ XRD and DSC provide information on the nucleation of PE crystals. For the first time, the in situ XRD technique was used for estimation of the coherent scattering region of PE blocks during the melting-crystallization cycles. These experiments and molecular dynamic modeling showed that MWCNTs act as the template for the PE chain orientation and as the nucleating agent for PE crystallization. However, the nucleation of PE crystals in composites occurs on the nanotube surface and also within the space between nanotubes. Thus, the relative volume of PE nucleated on nanotubes depends on their content in the composite and can be significant only for the composites with high nanotube loading.