The dilation-free semi-staggered finite volume method presented in Sabin [M. Sahin, A preconditioned semi-staggered dilation-free finite volume method for the incompressible Navier-Stokes equations on all-hexahedral elements, Int. J. Numer. Methods Fluids 49 (2005) 959-974] has been extended for the numerical solution of viscoelastic fluid flows on all-quadrilateral (2D) / hexahedral (3D) meshes. The velocity components are defined at element node points, while the pressure term and the extra stress tensor are defined at element centroids. The continuity equation is satisfied exactly within each element. An upwind least square method is employed for the calculation of the extra stresses at control volume faces in order to maintain stability for hyperbolic constitutive equations. The time stepping algorithm used decouples the calculation of the extra stresses from the evaluation of the velocity and pressure fields by solving a generalised Stokes problem. The resulting linear systems are solved using the GMRES method provided by the PETSc library with an ILU(k) preconditioner obtained from the HYPRE library. We apply the method to both two- and three-dimensional flow of an Oldroyd-B fluid past a confined circular cylinder in a channel with blockage ratio 0.5. Crown Copyright (C) 2007 Published by Elsevier B.V. All rights reserved.