The production reality of sheet steels from casting to the end product is such that in the cases of ultra- and advanced high-strength steels, we have to deal with the segregation of elements on macro- and microlevels. Both can have a significant impact on the microstructure formation and resulting properties. There are several production stages where it can influence the transformations, i.e., casting, hot rolling process and annealing after cold rolling. In the present work, we focus on the latter, and more specifically, the transformation from ferrite–cementite to austenite, especially the nucleation process, in cold-rolled material. We vary the levels of two substitutional elements, Mn and Si, and then look in detail at the microsegregation and nucleation processes. The classical nucleation theory is used, and both the chemical driving force and strain energy are calculated for various scenarios. In the case of a high Mn and high Si concentration, the nucleation can thus be explained. In the cases of high Mn and low Si concentrations as well as low Mn alloys, more research is needed on the nuclei shapes and strain energy.