Understanding chemical reactivity and magnetism of 3d transition metal nanoparticles is of fundamental interest for applications in fields ranging from spintronics to catalysis. Here, we present an atomistic picture of the early stage of the oxidation mechanism and its impact on the magnetism of Co nanoparticles. Our experiments reveal a two-step process characterized by (i) the initial formation of small CoO crystallites across the nanoparticle surface, until their coalescence leads to structural completion of the oxide shell passivating the metallic core; (ii) progressive conversion of the CoO shell to Co₃O₄ and void formation due to the nanoscale Kirkendall effect. The Co nanoparticles remain highly reactive toward oxygen during phase (i), demonstrating the absence of a pressure gap whereby a low reactivity at low pressures is postulated. Our results provide an important benchmark for the development of theoretical models for the chemical reactivity in catalysis and magnetism during metal oxidation at the nanoscale.