We have used a high-energy ball mill to prepare single-phased nanocrystalline Fe, Fe90Ni10, Fe85Al4Si11, Ni99Fe1 and Ni90Fe10 powders. We then increased their grain sizes by annealing. We found that a low-temperature anneal (T < 0.4 Tm) softens the elemental nanocrystalline Fe but hardens both the body-centered cubic iron- and face-centered cubic nickel-based solid solutions, leading in these alloys to an inverse Hall–Petch relationship. We explain this abnormal Hall–Petch effect in terms of solute segregation to the grain boundaries of the nanocrystalline alloys. Our analysis can also explain the inverse Hall–Petch relationship found in previous studies during the thermal anneal of ball-milled nanocrystalline Fe (containing ∼1.5 at.% impurities) and electrodeposited nanocrystalline Ni (containing ∼1.0 at.% impurities).