The enhanced stability of Co nanocrystals (NCs) when they are highly ordered at both nanometer and micrometer scales is reported. For the first time, it is shown that both the crystalline structure of Co nanoparticles (NPs) and their 2D hexagonal organization have a significant impact on the oxidation process rate enabling to produce various types of nanostructures including core-shell NPs. The Co core can be either polycrystalline or hexagonal close-packed (hcp) single-crystalline, whereas the oxide shell is composed either of CoO or of the spinel structrure Co3O4. The present results are evidenced through a careful high-resolution transmission electron microscopy (HRTEM) study and are highly reproducible.