Maleic anhydride-grafted polyethylene (MAPE) is investigated as a compatibilizer of polyethylene/organoclay nanocomposite. With MAPE help, partial exfoliation of the organoclay occurs in the nanocomposites with the melt compounding method for organoclay loading up to 8.0 wt%. Investigation of the rheological behaviors shows that at high frequencies or shear rates, the viscosity is essentially unaffected by the presence of organoclay; however, at low frequencies or shear rates, viscoelastic behavior alters dramatically, and this is attributed to the presence of anisotropic stacks of randomly oriented organoclay sheets and the formation of network structures. The important observations are firstly the initial stress overshooting observed in steady shear. At low shear rates, stress is much greater at the initial stage than the stress at the steady state; however, it can be eliminated by preshear at low shear rates, which means that preshearing can effectively break down the network structures and align the organoclay. Second, the normalized stress at the overshoot point is a function of the critical strain unit.