In this review paper the rheology of polymer nanocomposites with dispersed carbon nanotubes is presented. The major factors controlling the rheology of these nanocomposites are the overall concentration of the nanotubes and their state of dispersion. Percolation of anisotropic nanotubes and the transition from isotropic to nematic structures bound the range of concentrations over which the rheological properties of these nanocomposites is dominated by the meso-scale structure and dispersion and are of significance to the processing of nanotube based polymer nanocomposites. The percolation threshold and the concentration for the isotropic to nematic transition are strong functions of the inverse of the effective aspect ratio of the dispersed nanotubes and therefore restrict the range of concentrations over which such nanocomposites can be deployed. In this review we briefly describe the rheology in the dilute regime, where especially for the case of polymer nanocomposites the rheology is dominated by that of the polymer. Subsequently, the percolation phenomenon and rheological significances are presented. Finally, both linear and non-linear rheologies of semi-dilute dispersions with random orientation of nanotubes are discussed in detail. Where possible, the rheological responses are contextualized through the underlying structure of the nanocomposites and interplay of different forces.