The effect of annealing temperature on the permeability and giant magneto-impedance (GMI) behaviors of $Fe_{68.5}Mn_{5}Si_{13.5}B_9Nb_3Cu_1$ amorphous alloy has been systematically investigated. The nanocrystalline $Fe_{68.5}Mn_{5}Si_{13.5}B_9Nb_3Cu_1$ alloys consisting of ultra-fine $(Fe,Mn)_3Si$ grains embedded in an amorphous matrix were obtained by annealing their precursor alloy at the temperature range from $500^{circ}C;to;600^{circ}C$ for 1 hour in vacuum. The permeability and GMI profiles were measured as a function of external magnetic field. It was found that the increase of both the permeability and the GMI effect with increasing annealing temperature up to $535^{circ}C$ was observed and ascribed to the ultrasoft magnetic properties in the sample, whereas an opposite tendency was found when annealed at $600^{circ}C$ which is due to the microstructural changes caused by high-temperature annealing. The study of temperature dependence on the permeability and GMI effect showed some insights into the nature of the magnetic exchange coupling between nanocrystallized grains through the amorphous boundaries in nanocrystalline magnetic materials.