Microstructural and magnetic properties of nanocrystalline Fe-46 wt%Ni and Fe-36 wt%Ni alloys were investigated. Alloys were prepared by the electrodeposition process. The electrolytes were iron sulfate/nickel chloride-based and iron chloride/nickel sulfamate-based solutions. Fe-46 wt%Ni alloy was FCC structure with grain size of 10 nm, but FCC and BCC phases were found in Fe-36 wt%Ni alloy and its grain size was smaller. Effective permeability of Fe-36 wt%Ni alloy was higher than that of Fe-46 wt%Ni alloy in the high frequency range because of large electrical resistivity and small eddy current loss resulted from grain size decrease. Up to $300^{circ}C$ of annealing temperature, grain growth of Fe-Ni alloys slowly occured. Conversely, annealing above $450^{circ}C$ led to a drastic grain growth. In that case, effective permeability was decreased at the temperature lower than $300^{circ}C$ but at $300^{circ}C$ or higher effective permeability was increased. At the high frequency of 1 MHz, electrodeposited Fe-Ni alloys had higher effective permeability with an decrease in the grain size.