We consider the interaction of a moving planetary nebula (PN) with the interstellar medium. The PN shell is compressed first in the direction of the stellar motion. This produces a dipole asymmetry in the surface brightness of the nebula, typically at a nebular density of ∼40 cm-3 if the nebula is located in the Galactic plane. In the later stages of the interaction, this part of the shell is significantly decelerated with respect to the central star, and the PN becomes strongly asymmetric in shape. This distortion and the subsequent stripping of the nebular gas away from the central star typically occurs at a low nebular density of ∼6 cm-3. We examined the morphology of PNs with central stars whose proper motions exceed 0.015 arcsec yr-1 and found that many of the extended nebulae are interacting with the interstellar medium (ISM). Our sample doubles the number of known PNs interacting with the ISM. We examined the morphology of nearby PNs, and found a number of strongly asymmetric nebulae. We expect that the central stars in these PNs should have large proper motions, and we predict the directions from the observed asymmetries. We suggest the use of interacting PNs to determine the filling factor of the warm neutral and ionized components of the ISM.