We suggest a novel numerical algorithm based on the lattice Boltzmann method (LBM) to investigate particulate systems in which solid particles are suspended in a viscoelastic medium. In this model, polymer solution is described by the viscoelastic fluid based on the advection-diffusion LBM model, and it is coupled with the smoothed profile method (SPM) which describes the motion of rigid particles. To validate the present algorithm, we test three benchmark problems (two-dimensional simulation); viscoelastic flow past a cylinder, a single particle migration in a viscoelastic Couette flow, and dynamics of two particles in a viscoelastic Couette flow. Simulation results are carefully analyzed, and they are compared with previous simulation results implemented by finite element method (FEM) and finite volume method (FVM). In all test results, hydrodynamic properties and the motion of the particles induced by viscoelasticity are correctly captured, and they qualitatively as well as quantitatively correspond to previous reports. We conclude that both viscoelasticity and multi-body hydrodynamic interactions can be well incorporated in this new LBM algorithm. The present study has its significance as a first report, which strictly solves the flow behavior of solid particles immersed in a viscoelastic medium on the LBM framework. (C) 2017 Elsevier B.V. All rights reserved.