Polypropylene random copolymer nanocomposites having 0.2–7.0 vol% multi-walled carbon nanotubes (MWCNTs) were prepared via melt processing. Transmission electron microscopy (TEM) was employed to determine the nano scale dispersion of carbon nanotubes. Linear viscoelastic behavior of these nanocomposites was investigated using parallel plate rheometry. Incorporation of carbon nanotubes in the polymer matrix resulted in higher complex viscosity (η*), storage (G′) and loss modulus (G″) as compared to neat polymer, especially in the low-frequency region, suggesting a change from liquid to solid-like behavior in the nanocomposites. By plotting storage modulus vs. carbon nanotube loading and fitting with a power law function, the rheological percolation threshold in these nanocomposites was observed at a loading of ∼0.27 vol% of MWCNTs. However, electrical percolation threshold was reported at ∼0.19 vol% of MWCNTs loading. The difference in the percolation thresholds is understood in terms of nanotube connectivity with nanotubes and polymer chain required for electrical conductivity and rheological percolation.