Functionalization of multi-walled carbon nanotubes (MWCNTs) plays an important role in eliminating nanotube aggregation for reinforcing polymeric materials. We prepared a new class of natural rubber (NR)/MWCNT composites by using latex compounding and self-assembly technique. The MWCNTs were functionalized with mixed acids (H2SO4/HNO3 = 3:1, volume ratio) and then assembled with poly (diallyldimethylammonium chloride) and latex particles. The Fourier transform infrared spectroscopy, transmission electron microscopy, and scanning electron microscopy were used to investigate the assembling mechanism between latex particles and MWCNTs. It is found that MWCNTs are homogenously dispersed in the natural rubber (NR) latex as individual nanotubes since strong self-aggregation of MWCNTs has been greatly depressed with their surface functionalization. The well-dispersed MWCNTs produce a remarkable increase in the tensile strength of NR even when the amount of MWCNTs is only 1 wt.%. Dynamic mechanical analysis shows that the glass transition temperature of composites is higher and the inner-thermogenesis and thermal stability of NR/MWCNT composites are better, when compared to those of the pure NR. The marked improvement in these properties is largely due to the strong interfacial adhesion between the NR phase and MWCNTs. Functionalization of MWCNTs represents a potentially powerful technology for significant reinforcement of natural rubber materials.