We propose a novel algorithm for velocity reconstruction from staggered data on arbitrary polygonal staggered meshes. The formulation of the new algorithm is based on a constant polynomial reconstruction approach in conjunction with an iterative defect correction method and is referred to as the IDeC(k) reconstruction. The algorithm is designed for second order accuracy of the reconstructed velocity field and also leads to a consistent estimate of velocity gradients. Accuracy, convergence and robustness of the new algorithm are studied on different mesh topologies and the need for higher-order reconstruction is demonstrated. Numerical experiments for several cases including incompressible viscous flows establish the IDeC(k) reconstruction as a generic, fast, robust and higher-order accurate algorithm on arbitrary polygonal meshes. © 2011 Elsevier Inc.