We present Herschel-SPIRE observations of the perturbed galaxy NGC 4438 in the Virgo cluster. These images reveal the presence of extra-planar dust up to ~4-5 kpc away from the galaxy's disk. The dust closely follows the distribution of the stripped atomic and molecular hydrogen, supporting the idea that gas and dust are perturbed in a similar fashion by the cluster environment. Interestingly, the extra-planar dust lacks a warm temperature component when compared to the material still present in the disk, explaining why it was missed by previous far-infrared investigations. Our study provides evidence for dust stripping in clusters of galaxies and illustrates the potential of Herschel data for our understanding of environmental effects on galaxy evolution. Herschel is an ESA space observatory with science instruments provided by European-led Principal Investigator consortia and with important participation from NASA.