Nanocrystalline materials have a variety of new or improved properties compared to their single crystalline counterparts [1]. Severe plastic deformation and solute segregation to grain boundaries are useful and simple methods to produce nanocrystalline materials. Examples for nanocrystalline iron doped with various solutes (carbon, nitrogen, oxygen and boron) and various concentrations are presented. The alloys were generated by ball milling iron powder with graphite, iron boride, iron nitride and iron oxide and their grain size was determined with transmission electron microscopy. Severe plastic deformation by wire drawing of Pearlite also leads to a nanocrystalline Fe-C alloy. All alloys had a grain size of about 20 nm. Results of the thermal stability of the alloys with respect to phase separation and coarsening is provided. Based on Gibbs Adsorption Isotherm the dependence of grain size on solute concentration is explained. It will be shown that Gibbs Adsorption Isotherm can be generalized [2] from surfaces and grain boundaries to all kinds of discontinuities (dislocations, vacancies etc.).