A new algorithm to recover centroidal velocities from face-normal data on two-dimensional unstructured staggered meshes is presented. The proposed approach uses iterative defect correction in conjunction with a lower-order accurate Gauss reconstruction to obtain second-order accurate centroidal velocities. We derive the conditions that guarantee the second-order accuracy of the velocity reconstruction and demonstrate its efficacy on arbitrary polygonal mesh topologies. The necessity of the proposed algorithm for non-Newtonian flow simulations is elucidated through numerical simulations of channel flow, driven cavity and backward facing step problems with power-law and Carreau fluids. Numerical investigations show that second-order accuracy of the reconstructed velocity field is critical to obtaining physically consistent solutions of vorticity-dominated flows on non-orthogonal meshes. It is demonstrated that the spurious solutions are not linked to discrete conservation and arise solely due to the lower order accuracy of velocity reconstruction. The importance of the proposed algorithm for hemodynamic simulations is highlighted through studies of laminar flow in an idealized stenosed artery using different blood models. © 2014 Elsevier Inc.