The characteristics of domain wall propagation in Fe73.5Cu1Nb3Si13.5B9 amorphous and nanocrystalline glass-coated microwires are investigated in order to determine the changes induced by structural transformation in wall velocity and mobility. An improved method for sensing the wall presence and direction, and for measuring its velocity, is also presented. Amorphous samples are bistable, and their wall velocity displays typical values for microwires with positive magnetostriction. Nanocrystallized samples are not bistable in general, but they become bistable either if the glass coating thickness is large enough to induce a strong axial anisotropy, or if their metallic nucleus diameter is large enough to increase the contribution of the magnetostatic term. Bistable nanocrystalline microwires display smaller switching field values, together with larger wall velocity and mobility values as compared to bistable amorphous samples with the same composition. The results have been explained considering the changes induced in magnetostriction by the nanocrystalline phase formation and the magnetization reversal mechanism by means of wall propagation.