New magnetic nanocrystalline powders (Fe75Al25)100-xBx(x = 0, 5, 9, 12) were prepared by mechanical alloying. The boron content and milling time affect the magnetic and structural properties of these alloys. Morphological, microstructural, structural, thermal and magnetic characterizations of powders that were milled for different times were investigated by scanning electron microscopy, X-ray diffraction, vibrating sample magnetometry and SQUID techniques. The formation of two crystalline phases was observed with increasing boron content. The major phase corresponds to an FeAl bcc phase, and the second phase, with lower content, corresponds to an FeB phase, which required additional milling time. With increasing milling time, the crystallite size decreased to the nanoscale level, whereas the microstrain and lattice parameter of the disordered solid solution increased. A decrease in coercivity (Hc) with increasing boron content was also observed. These variations are explained based on crystallite size and strain variation in the samples during milling.