An unsolved issue in the standard core accretion model for gaseous planet formation is how kilometre-sized planetesimals form from,initially, micron-sized dust grains. Solid growth beyond metre sizes can be difficult both because the sticking efficiency becomes very small,and because these particles should rapidly migrate into the central star. We consider here how metre-sized particles evolve in self-gravitating accretion discs using simulations in which the gravitational influence of the solid particles is also included. Metre-sized particles become strongly concentrated in the spiral structures present in the disc and, if the solid to gas density ratio is sufficiently high, can fragment because of their own self-gravity to form planetesimals directly. This result suggests that planetesimal formation may occur very early in the star formation process while discs are still massive enough to be self-gravitating. The dependence of this process on the surface density of the solids is also consistent with the observation that extrasolar planets are preferentially found around high-metallicity stars.