A direct simulation methodology for solid spheres moving through viscoelastic (FENE-CR) fluids has been developed. It is based on a lattice-Boltzmann scheme coupled with a finite volume solver for the transport equation of the conformation tensor, which directly relates to the elastic stress tensor. An immersed boundary method imposes no-slip conditions on the spheres moving over the fixed grid. The proposed method has been verified by comparison with computational data from the literature on the viscoelastic flow past a stationary cylinder. Elastic effects manifest themselves in terms of drag reduction and for-aft asymmetry around the cylinder. Single sphere sedimentation in viscoelastic fluids shows velocity over-shoots and subsequent damping before a steady settling state is reached. In multi-sphere simulations, the interaction between spheres depends strongly on the (elastic) properties of the liquid. Simulations of sedimentation of multiple spheres illustrate the potential of the method for application in dense solid-liquid suspensions. The sedimentation simulations have Reynolds numbers of order 0.1 and Deborah numbers ranging from 0 to 1.0. (C) 2012 Elsevier B.V. All rights reserved.