Nucleation during solidification in multi-component alloys is a complex process that comprises competition between different crystalline phases as well as chemical composition and ordering. Here, we combine transition interface sampling with an extensive committor analysis to investigate the atomistic mechanisms during the initial stages of nucleation in Ni3Al. The formation and growth of crystalline clusters from the melt are strongly influenced by the interplay between three descriptors: the size, crystallinity, and chemical short-range order of the emerging nuclei. We demonstrate that it is essential to include all three features in a multi-dimensional reaction coordinate to correctly describe the nucleation mechanism, where, in particular, the chemical short-range order plays a crucial role in the stability of small clusters. The necessity of identifying multi-dimensional reaction coordinates is expected to be of key importance for the atomistic characterization of nucleation processes in complex, multi-component systems.