This article investigates the effect of shear-thinning viscosity on chaotic mixing when the kinematics first begin to deviate from Newtonian flow. Computations are done for a 2-D, time-periodic flow between eccentric cylinders. The effectiveness of mixing is analyzed by examining the asymptotic coverage of a passive tracer, character and location of periodic points, and the rate of stretching of fluid elements. Small variations in the velocity field associated with non-Newtonian kinematics produce large effects in the chaotic advection of a passive tracer. The stretching rate remains exponential, but with a long time constant as the shear-thinning effect increases, often resulting in the birth of new periodic islands and a decrease in the asymptotic coverage of the tracer. Exceptions to these observations are possible : both the stretching rate and the asymptotic coverage might increase as shear thinning increases. Results also indicate that suitable manipulation of operating conditions can produce shear-thinning flows which mix as well as Newtonian flows. Since significant effects are observed with less than a 4% difference in the velocity fields, the assumption of Newtonian kinematics can lead to large errors in the design and operation of process mixing equipment for non-Newtonian fluids.