The evolution of the structure of glass-coated Fe40Ni38Mo4B16 amorphous microwire with thermal treatments and its interplay with magnetism has been studied. As shown by x-ray diffraction, a primary crystallization process resulted into formation of γ-(Fe,Ni) nanocrystallites embedded in a residual amorphous matrix. The evolution of the saturation magnetization and the switching field after different thermal treatment was studied. Amorphous glass-coated microwires based on FeNi exhibit magnetic bistability even in the nanocrystalline state. This is explained by the high magnetoelastic anisotropy, which is also responsible for magnetic hardening after annealing at the temperatures above 670 K.