We have discovered two novel aspects of the stripe-domain to paramagnetic transition in perpendicularly magnetized Fe films on Cu(100). First, the width of the stripes carrying oppositely oriented spins decreases, close to the transition temperature, with a power law. Second, in a small temperature interval close to the transition temperature, the stripes--which form stationary patterns at low temperatures--become mobile. Various theoretical works have predicted stripe mobility in similar frustrated systems but no direct proof of this phenomenon has been reported so far.