We investigated the effects of soft dendritic polyethylene (dPE) nanopartides on the theological properties of a linear polystyrene (PS). matrix. The viscosity of PS-dPE nanocomposites is found to exhibit nonmonotonic dependence on the dPE concentration. In particular, with the addition of 1% dPE nanopartides, we already observe more than 1 order of magnitude reduction in viscosity. The minimum viscosity was observed at 5% nanopartides. At dPE concentrations higher than 5%, nanocomposite viscosity increases by addition of nanopartides, yet it remains below the viscosity of PS. Addition of nanopartides not only influences the terminal relaxation times of the nanocomposites but also affects their whole relaxation spectra. The viscosity of PS dPE nanocomposites at high temperature is found to reversibly evolve with time, which proves the existence of supramolecular interactions between the PS matrix and the nanopartides. Atomic force microscopy confirms that dPE nanopartides are well distributed in the PS matrix, though each component of the nanocomposite exhibits its own glass transition. While the origin of viscosity reduction remains unknown, it cannot be attributed to confinement, free volume effect, change of entanglement density, surface slippage, shear banding, or particle induced shear thinning.