Functionalization of carbon nanotubes is considered as an essential step to enable their manipulation and application in potential end-use products. In this paper we introduce a new approach to functionalize multiwalled carbon nanotubes (MWNTs) by applying an amidation-type grafting reaction with amino-functionalized alternating polyketones. The functionalized MWNTs were characterized by using thermogravimetric analysis (TGA), X-ray photoemission spectroscopy (XPS), element analysis, Raman spectroscopy, scanning electron microscopy (SEM), and transmission electron microscopy (TEM). Around 40 wt % polyamines based on the total weight of the MWNTs can be covalently attached to the surface of the MWNTs. It is found that polyamines act as cross-linking agents to interconnect or cross-link the MWNTs within and between bundles, as demonstrated by SEM and TEM analysis. After cross-linking, the functionalized MWNTs are insoluble in any solvent. The cross-linked MWNTs can be melt-blended into polyethylene, and the resulting composites show comparable mechanical properties to those obtained by simple blending of “un-cross-linked” nanotubes with polyethylene.