Fe-Ga alloys are attractive magnetostrictive materials due to large magnetostriction along <100> direction and high mechanical strength. However, sharp Goss ({110}<001>) texture and large magnetostriction coefficients were conventionally achieved by secondary recrystallization with centimeter-sized grains under the effects of inhibitor and surface energy, resulting in deteriorated mechanical properties. Texture optimization in relatively fine grained microstructure is an effective way to obtain excellent comprehensive properties. Cold rolling process can determine the difference in number and size of primary recrystallization grains among various texture components, and further influence the texture and grain size evolution during subsequent high temperature annealing. The present work aims to produce strong η texture (<001>//RD, rolling direction) in binary Fe-Ga sheet with relatively fine recrystallization grains by cold rolling parameter modification. Macro- and micro-texture analysis was applied to investigate the effects of primary recrystallization states on texture and grain size evolution during high temperature annealing in binary Fe-Ga sheet. The η grains can gain more numbers and relatively larger sizes in primary recrystallization stage, and preferably grow even abnormally during high temperature annealing. A sharp η texture and large magnetostriction coefficient are successfully developed in primarily and secondarily recrystallized sheets with relatively fine grains. The results provide a prospective route for the efficient recrystallization texture and grain size optimization in binary Fe-Ga and other bcc alloys.