An implicit Newton-Krylov finite volume algorithm has been developed for efficient steady-state computation of the power-law non-Newtonian fluid flows. The pseudo-compressibility technique is used for the coupling of continuity and momentum equations. The spatial discretization is central (second-order) for both convective and diffusive terms and the accuracy of the solution is verified. The nine block diagonal Jacobian matrix (needed for implicit formulation) is computed directly through the flux differentiation. Five-diagonal and three-diagonal block matrices (the simplified versions of the main Jacobian matrix) are used with the ILU(0 & 1) and the Thomas linear solvers for preconditioning, respectively. The performance of the Newton-GMRES solver is examined in detail for different preconditioning strategies. The effects of the power-law behavior index and Re number on the convergence rate are also studied. The performance of the Newton-BiCGSTAB and the Newton-GMRES solvers are compared with each other. The results show, the ILU(1)/Newton-GMRES is the most efficient combination that is robust even in high Reynolds number shear-thinning fluid flow cases. (C) 2011 Elsevier B.V. All rights reserved.