We have obtained Herschel images at five wavelengths from 100 to 500 micron of a ~5.5x2.5 degree area centred on the local galaxy M31 (Andromeda), our nearest neighbour spiral galaxy, as part of the Herschel guaranteed time project HELGA. The main goals of HELGA are to study the characteristics of the extended dust emission, focusing on larger scales than studied in previous observations of Andromeda at an increased spatial resolution, and the obscured star formation. In this paper we present data reduction and Herschel maps, and provide a description of the far-infrared morphology, comparing it with features seen at other wavelengths. We use high--resolution maps of the atomic hydrogen, fully covering our fields, to identify dust emission features that can be associated to M31 with confidence, distinguishing them from emission coming from the foreground Galactic cirrus. Thanks to the very large extension of our maps we detect, for the first time at far-infrared wavelengths, three arc-like structures extending out to ~21, ~26 and ~31 kpc respectively, in the south-western part of M31. The presence of these features, hosting ~2.2e6 Msol of dust, is safely confirmed by their detection in HI maps. Overall, we estimate a total dust mass of ~5.8e7 Msol, about 78% of which is contained in the two main ring-like structures at 10 and 15 kpc, at an average temperature of 16.5 K. We find that the gas-to-dust ratio declines exponentially as a function of the galacto-centric distance, in agreement with the known metallicity gradient, with values ranging from 66 in the nucleus to ~275 in the outermost region. [Abridged]