Combining density functional theory, Nudged Elastic Band, and high-energy resolution x-ray photoelectron spectroscopy experiments, we study the early stages and reaction pathways whereby ethylene molecules decompose on Ni3Al (111) prior to graphene nucleation and growth. After characterizing stable configurations of ethylene on the surface, as well as of all intermediate products leading to carbon species, we calculate energy barriers for all relevant processes, including dehydrogenation, isomerization, C-C cleavage and their respective inverse reactions. This quantitative analysis helps in identifying the most probable reaction pathways. The combination of temperature dependent C 1s core level photoelectron spectroscopy measurements and of core level shift calculations for all the different species investigated allowed us to understand the temperature evolution of the surface species, and to identify the whole reaction mechanism. Combined analysis of this kind is useful for understanding which species are present on the surface at various temperatures during chemical vapor deposition graphene growth experiments.