Linear low density polyethylene (LLDPE)/multi-walled carbon nanotube (MWCNT) composites were prepared by melt compounding, following two different compatibilization strategies that involved non-covalent interactions between the matrix and the filler. The first approach involved grafting pyridine aromatic moieties on the maleated polyolefin backbone, which are able to interact by π–π stacking with the surface of the nanotubes. The second method implemented non-covalent/non-specific surface functionalization of the MWCNTs with a hyperbranched polyethylene (HBPE). The enhanced interfacial interactions established in the composites containing LLDPE functionalized with pyridine grafts improved the dispersion of the nanotubes within the polymer matrix. Dispersion was also favoured by higher matrix viscosity. Composites containing finely dispersed MWCNTs exhibited an increase in the rheological and electrical percolation thresholds, and a significant improvement in mechanical properties. On the contrary the composites based on the low viscosity matrix contained large amounts of aggregates, which promoted lower percolation thresholds. Manipulation of matrix viscosity and compatibilization resulted in composites with good mechanical properties, and low percolation thresholds.