The results from a large field Far-Infrared (FIR) and sub-millimeter (sub-mm) survey of our neighbor galaxy M31 are presented. We have obtained Herschel images of a ~5.5x2.5 degree area centered on Andromeda. Using 21 cm atomic hydrogen maps, we are able to disentangle genuine emission from M31 from that for foreground Galactic cirrus, allowing us to recognize dusty structures out to ~31 kpc from the center. We first characterize the FIR and sub-mm morphology and then, by de-projecting Herschel maps and running an ad--hoc source extraction algorithm, we reconstruct the intrinsic morphology and the spatial distribution of the molecular complexes. Finally, we study the spatially resolved properties of the dust (temperature, emissivity, mass, etc.), by means of a pixel-by-pixel SED fitting approach.